Shellsort is not O(n log n) but not O(n^2) either
softpanorama.org
I thought I recalled Knuth showing shellsort was better than O(n^2), but worse than O(n log n). According to this page, shellsort is somewhere around N(log N)^2 and N^(1.25). The proof is in Knuth, TAOCP.