コムソート
動作例として
8 4 3 7 6 5 2 1
という数列を昇順に整列してみる。 このとき n=8 だから h=8÷1.3≒6 から始める。 8と2、4と1を比較して2回交換を行う。
8 4 3 7 6 5 2 1
2 4 3 7 6 5 8 1
2 1 3 7 6 5 8 4
次は h = 6÷1.3 ≒ 4。2と6、1と5のように比較してゆき、7と4のみが交換される。
2 1 3 7 6 5 8 4
2 1 3 4 6 5 8 7
以下 h は 3 → 2 → 1 の順に減っていくので
h=3:交換なし
2 1 3 4 6 5 8 7
h=2:交換なし
2 1 3 4 6 5 8 7
h=1:交換3回
2 1 3 4 6 5 8 7
1 2 3 4 6 5 8 7
1 2 3 4 5 6 8 7
1 2 3 4 5 6 7 8
この例では6回の交換で整列が終了した。