奇偶転置ソート

奇偶転置ソート（きぐうてんちソート、Odd-even Sort）は、ソートのアルゴリズムの一つで、バブルソートを、改良したもの。バブルソートではスキャンを一方向に順次行うのに対し、奇偶転置ソートではペアごとに行う。バブルソートと同じく安定な内部ソートで、最悪の場合の時間計算量はO(n)である。ペアの比較は互いに独立であるため、バブルソートとは異なり、並列動作が可能である。