これも素朴なソートの一種であるが、Shell ソートの中で使うので取りあげる。
最も lucky な場合、比較回数は N-1, 交換回数は 0 である。 最悪の場合、どちらもおよそ N2/2. 平均すればどちらもおよそ N2/4 とみてよいだろう。 どちらもΟ(N2) である。 前のアルゴリズムと異なり、 もしも配列がほとんどソートされていれば比較回数も交換回数も小さいことに注意。
（正の）自然数 m を一つ選んで固定する。 配列 a[0], ..., a[N-1] を次の m 本の部分配列に分割する。
m < M とするとき、次の事実が成り立つ。
M おきにソートしてから m おきにソートした結果は、M おきにソートされている。
（証明のアウトライン： 「m おき（の）転倒数」を # {(i, j) | i < j かつ j-i は m の倍数、かつ a[i] > a[j]} で定義する。 いま、配列は M おきにソートされているとしよう。 m おきの転倒数が 0 でなければ、m おきのソートは完了していない。 そのとき、j-i がちょうど m に等しくかつ転倒している組がある。 それを a[i], a[i+m] としたとき、 組 a[i+k*M], a[i+m+k*M] （M は整数）のうち、転倒している組をすべて交換する。 この操作のあと、m おき転倒数が減少していることは明らかだが、 M おきにソートされたままであることを観察せよ。 この操作をくり返してゆけば m おきのソートが完了するのだから、 主張は正しい。 なお、 実際のプログラムで m おきのソートを行なう際にはこの手順に従う必要は全くない。）
よって、 M おきにソートしてから m おきにソートしたあとでは、 任意の i に対し、 x, y を 0 以上の整数とするとき、a[i] <= a[i+m*x+M*y] が成り立つ。 ここで、たとえば m = 3, M = 5 としてみると、 x, y をうまく選ぶことで、m*x+M*y にはいろいろな値をとらせることができる。 例：「3 = 3*1+5*0, 5 = 3*0+5*1, 6 = 3*2+5*0, 8 = 3*1+5*1, 9 = 3*3+5*0, 10 = 3*0+5*2, 11 = 3*2+5*1, 12 = 4*3+5*0, 13 = 1*3+5*2」。
次の定理は Chinese Remainder Theorem として知られている。
a と b を互いに素な自然数とし、 d を整数とするとき、 方程式 ax+by = d は整数解 (x, y) をもつ。
ことばを変えて言えば、a と b とが互いに素なら、 直線 ax+by = d の上には格子点（= x 座標も y 座標も整数である点）が存在する、 ということである。 (x, y) が解であるとき、任意の整数 k に対し (x+kb, y-ka) も解である。 これ以外の解はないことはすぐわかる。 よって、格子点は直線 ax+by = d のうえに x 座標でみて b おき、y 座標でみて a おきに並んでいる。
a と b を互いに素な自然数とするとき、整数 d が (a-1)(b-1) 以上ならば 方程式 ax+by = d は 0 以上の整数の解 (x, y) をもつ。
（証明のアウトライン： 直線 ax+by = d のうえに格子点があることは上の定理の主張である。 この直線は、d が大きくなるほど上方へ移動する。 d = (a-1)(b-1) のとき、 直線 y = -1 とは x = b-1+1/a で交わる。 これと x = -1 との差は b+1/a となり、b よりも大きい。 d がより大きければ、この差はさらに大きくなる。 よって、d が (a-1)(b-1) 以上であるならば、 直線 ax+by = d のうち x > -1 かつ y > -1 の部分に格子点があることがわかる。）
5 おきにソートし、次に 3 おきにソートした場合、 k >= 8 ならば a[i] < a[i+k] であることがわかった。 最後に 1 おきの挿入ソートを行なう。 このとき、 どの要素を挿入する際にも 8 回以上の交換を行なう必要はないことに注意したうえで、 計算量をおおざっぱに調べてみよう。 5 おきのソートの計算量は 5(N/5)2/4 = N2/20 であり、 3 おきのソートの計算量は 3(N/3)2/4 = N2/12 である。 これに最後の 1 おきのソートの計算量 7N を加えると 2N2/15 + 7N となる。 Ο(N2) であることに変わりはないが、 N2 の係数が小さくなった分だけ速くなった。
実際には、 m を単調に減少させながら、もっと何度も「m おきのソート」を行なう。 たとえば、 「m を漸化式 m[1] = 1, m[n+1] = 3 * m[n] + 1 で定義される数列 1, 4, 13, 40, 121, 364, ...」の元に選ぶとよいらしい。 m が N 以上ならば「m おきのソート」とは何もしないことだから、 N を越えない最大の項から始めればよい。
また、上では m 本の部分数列をそれぞれ m おきにソートすると説明したが、 実際には
以下の二つのプログラムは課題ではない。 いずれも、 前回の素朴なソートのプログラム（をコピーしたもの） を（少々）書き直せばよいだろう。
1) 挿入ソートのプログラムを書け。 余力があれば、交換回数や比較回数を実験で調べよ。
2) Shell ソートの下準備のため、 「初項 1 と漸化式 m[n+1] = 3 * m[n] + 1 とで定義される数列の項を最初に N 以上になるまで出力し、 その一つ前の項を出力し、 そこから逆に初項まで戻って出力するプログラム」を書け。
出力例：
N は 50 です. 1 4 13 40 121 となって N 以上になりました. 40 から始めます。 40 13 4 1
N は #define で定義する定数とする。 上では数列を配列のように書いたがそれは説明の都合であり、 配列にする必要はない。一つの int 型変数とすれば十分である。
ヒント：
m = 1;
while (m < N) {
....
m = 3 * m + 1;
....
}
for (m = m/3; m > 0; m = m/3) {
...
}
課題 5-1) 課題 4-1 と同様のことを、Shell ソートについて調べよ。
課題 5-2) 課題 4-2 と同様のことを、Shell ソートについて調べよ。
※ Shell ソートのプログラムを試す際には、 最初から配列を画面いっぱいにとること。 10 ぐらいでは意味がない。 また、途中で m が変わるごとに 「40 おきにソートします」 などと出力させるとよいかもしれない。 （これらの間にソートされてゆく過程が出力されることになる。）
以上から適当に選んで、メールでレポートしてください。
プログラムも送ってください。 その際、Active!Mail のメール作成画面の「添付ファイル」 *ではなく* 本文の中にソースファイルを貼りつけること。
所要時間を計るにせよ回数を数えるにせよ、 数回くり返して測定し、それらのデータそのものおよび平均値をレポートに書くこと。 それから、理論上の値などと比較すること。 感想は書かなくてもよい。
宛て先は私（岩瀬）の実習用アカウント cf5326@mailedu1.ipc.kanazawa-u.ac.jp です。 件名は「kadai5」（←全て半角文字、アルファベットは小文字、 途中にスペースをいれない）としてください。 自分の学籍番号、氏名（として大学に届けてあるもの） をメールの *本文内にも* 書くのを忘れずに。
これも、提出用の課題ではありません。
1) 挿入ソートの二段目は、次のようにも書ける。
2) 配列を 「ほとんどソートされている」 あるいは 「ほとんど逆順にソートされている」 ように初期化する方法を考えよ。 そのように初期化した場合、挿入ソートの交換回数などはどのようになるか。 実験もして調べよ。
3) Shell ソートの m の取り方を別のものに変えたらどうなるか。 効率を調べてみよ。 （K&R2 の教科書に出ているのは効率がよくないと言われている。 それを確かめてみるのもよい。）
1) 添字が配列の外を指すミスがあると、 ソートしているうちに 0 がはいってくることがある。 そうかどうかはっきりさせるために、 0 から 99 まででなく、 1 から 99 までで初期化するほうがよかったかもしれない。
2) プログラムのどこかに 「printf("配列の大きさは %d です.\n", N);」 をいれておくとよいかもしれない。 こうすると、 配列の大きさをいろいろ変えて実験する際、 コンパイルし忘れた、などのミスが避けられる。