奇偶転置ソート

奇偶転置ソート（きぐうてんちソート、英: odd-even sort）は、ソートのアルゴリズムの一つで、バブルソートを改良したもの。バブルソートではスキャンを一方向に順次行うのに対し、奇偶転置ソートでは組ごとに行う。 バブルソートと同じく安定な内部ソートで、最悪の場合で時間計算量はO(n2)である。 組の比較は互いに独立であるため、バブルソートとは異なり、並列動作が可能である。そのため、ハードウェアで隣り合う組の比較を同時に処理すれば、常に (n-1) ステップで処理が完了する。ただし、ソートの対象が多いと必要とするリソースが大きくなり、実用的ではない。