奇偶転置ソート（きぐうてんちソート、）は、ソートのアルゴリズムの一つで、バブルソートを、改良したもの。バブルソートではスキャンを一方向に順次行うのに対し、奇偶転置ソートではペアごとに行う。バブルソートと同じく安定な内部ソートで、最悪の場合の時間計算量はO(n)である。ペアの比較は互いに独立であるため、バブルソートとは異なり、並列動作が可能である。奇偶置換ソートは、奇数番目とその次の偶数番目をペア (Pair1) にして比較／交換した後、偶数番目とその次の奇数番目をペア (Pair2) にして比較／交換することを繰り返すアルゴリズムである。Pair1:（1番目と2番目を比較、3番目と4番目を比較、5番目と6番目を比較、…）の後にPair2:（2番目と3番目を比較、4番目と5番目を比較、6番目と7番目を比較、…）を行う。これを繰り返す。1番目が i=0 になっているのはC言語の仕様。下線は比較（と交換）されたデータのペアを示す。初期データ: 8 4 3 7 6 5 2 18 4 3 7 6 5 2 11回目のスキャン終了後:（Pair1/交換回数:3）4 8 3 7 5 6 1 24 8 3 7 5 6 1 22回目のスキャン終了後:（Pair2/交換回数:3）4 3 8 5 7 1 6 24 3 8 5 7 1 6 23回目のスキャン終了後:（Pair1/交換回数:4）3 4 5 8 1 7 2 63 4 5 8 1 7 2 64回目のスキャン終了後:（Pair2/交換回数:2）3 4 5 1 8 2 7 63 4 5 1 8 2 7 65回目のスキャン終了後:（Pair1/交換回数:3）3 4 1 5 2 8 6 73 4 1 5 2 8 6 76回目のスキャン終了後:（Pair2/交換回数:3）3 1 4 2 5 6 8 73 1 4 2 5 6 8 77回目のスキャン終了後:（Pair1/交換回数:3）1 3 2 4 5 6 7 81 3 2 4 5 6 7 88回目のスキャン終了後:（Pair2/交換回数:1）1 2 3 4 5 6 7 8交換回数:3+3+4+2+3+3+3+1=22（バブルソートと同じ）

出典:wikipedia