シェルソート
概要
挿入ソートの強化版的なやつです． $n$ を配列の長さ，$h$ を適当に大きな $n$ 未満の自然数とします． まず，要素をインデックスを $h$ で割ったあまりによって分類し $n/h$ 程度の列を $h$ 個作ります． 具体的には $[a\_0, a\_h, a\_{2h} , \cdots], [a\_1, a\_{h+1}, a\_{2h+1} , \cdots ], \cdots$ のようになります． そしてそれぞれに対して挿入ソートを行います．これを $h$ を適当に減少させて何度かやりなおし，$h = 0$ となったらやめます．
部分に対するソートを繰り返す度に全体がだいたいソートされて行きます． 挿入ソート自体の計算量は $O(n^2)$ と良くないのですが，列がだいたいソートされていると高速であるという特性があるため，全体として最悪でも下に示したような計算量になるそうです． よく理解していませんが $h$ には $h' = 3h+1$ で生成される数列などを使うとよいらしいです．
実装が簡単で計算量もそこそこ良いので書かないといけないときはこれがベストかもしれないです．
計算量
$O(n (\log n)^2)$
実装
template <typename T>
void shellsort(T *l, T *r) {
int n = r - l, h = 1;
while (3 * h + 1 < n) h = 3 * h + 1;
for (; h != 0; h = (h - 1) / 3)
for (int i = 0; i < h; i++)
for (int j = i + h; j < n; j += h)
for (int k = j; k != i && l[k - h] > l[k]; k -= h) swap(l[k], l[k - h]);
}