コムソートを使用する

コムソート (comb sort) は、一定の間隔（ギャップ）で離れた2要素どうしを比較し、逆順なら交換する操作を繰り返す比較ソートである。

間隔をだんだん狭め、最終的に間隔 1（隣同士）の走査だけが残ると、振る舞いはバブルソート に近づく。粗い間隔から先に大まかな秩序を作るため、同じ O(n²) 系でもバブル単体より実効速度が出やすい。

  1. ギャップの設定: 配列長 n から出発し、各フェーズでギャップを縮小係数（典型値は約 1.3）で割り、1 未満になる場合は 1 に丸める。
  2. 走査と交換: 索引 i について A[i] と A[i + gap] を比較し、A[i] > A[i + gap] なら交換する。i を 0 から n - 1 - gap まで進める。
  3. 繰り返し条件: ギャップが 1 より大きい または、直前のフェーズで交換が一度でも起きた限り、手順 1〜2 を続ける。ギャップが 1 で、交換のない走査が終われば完了。

Lacey と Box が提案した経験的な縮小率 1.3 に加え、小さなギャップが 9 または 10 になることを避ける Comb sort 11を併用する実装がよく知られている。

procedure comb_sort(A)
  n = length(A)
  gap = n
  shrink = 1.3
  swapped = true
  while gap > 1 or swapped
    gap = floor(gap / shrink)
    if gap < 1 then
      gap = 1
    if gap == 9 or gap == 10 then   // Comb sort 11
      gap = 11
    swapped = false
    for i from 0 to n - 1 - gap
      if A[i] > A[i + gap] then
        swap(A[i], A[i + gap])
        swapped = true

最悪時間計算量は O(n²) だが、バブルソートに比べ「遠く離れた大きい値・小さい値」の入替えが早い。空間計算量は O(1) のインプレース、等しいキーの順序は一般に保証されない 不安定 ソートである。