奇偶転置ソートを使用する

奇偶転置ソート (odd-even sort) は、2種類の組に分けて隣接要素同士だけを比較し、逆順なら交換する操作を繰り返す比較ソートである。

  1. 偶数組: インデックス (0,1), (2,3), (4,5), … のペアを左サイドから順に見て、右の要素の方が小さければ入れ替える。
  2. 奇数組: インデックス (1,2), (3,4), (5,6), … のペアについて同様に比較・交換する。
  3. 収束: 偶数組と奇数組をまとめて 1 ラウンドとみなし、あるラウンドで一度も交換が起きなければ全体は昇順に整っているので終了する。

隣接ペアだけを同時に処理できるため、同じ組内の比較・交換は互いに干渉せず、ラウンド内では「飛び飛びのペア」をまとめて進められる点が特徴である。

逐次実行では最悪時間計算量は O(n²)（ラウンド数は O(n)、各ラウンドで O(n) 本の隣接ペア）、追加の配列を使わず O(1) の補助記憶でよい インプレース な実装が可能である。隣接交換のみで 安定 なソートになる。クイックソートのような分割再帰型と比べれば遅いが、構造が単純でデバッグや可視化向きである。

procedure odd_even_sort(A)
  n = length(A)
  sorted = false
  while not sorted
    sorted = true
    for i from 0 to n - 2 by 2
      if A[i] > A[i + 1] then
        swap(A[i], A[i + 1])
        sorted = false
    for i from 1 to n - 2 by 2
      if A[i] > A[i + 1] then
        swap(A[i], A[i + 1])
        sorted = false

偶・奇の相に分けて常に隣同士だけを見るため、バブルソートと並べると「先頭から順に走査するか、飛び飛びのペアで進めるか」の違いがはっきりする。