奇偶排序1972

该算法中，通过比较数组中相邻的（奇-偶）位置数字对，如果该奇偶对是错误的顺序（第一个大于第二个），则交换。下一步重复该操作，但针对所有的（偶-奇）位置数字对。如此交替进行下去。

处理器数组的排序

在并行计算排序中，每个处理器对应处理一个值，并仅有与左右邻居的本地互连。所有处理器可同时与邻居进行比较、交换操作，交替以奇-偶、偶-奇的顺序。该算法由Habermann在1972年最初发表并展现了在并行处理上的效率。

该算法可以有效地延伸到每个处理器拥有多个值的情况。在Baudet–Stevenson奇偶合并分割算法中，每个处理器在每一步对自己所拥有的子数组进行排序，然后与邻居执行合并分割或换位合并。

Batcher奇偶归并排序

Batcher奇偶归并排序是一种相关但更有效率的排序算法，采用比较-交换和完美-洗牌操作。

Batcher的方法在拥有广泛互连的并行计算处理器上效率不错。

In computing, an odd–even sort or odd–even transposition sort (also known as brick sort or parity sort) is a relatively simple sorting algorithm, developed originally for use on parallel processors with local interconnections. It is a comparison sort related to bubble sort, with which it shares many characteristics. It functions by comparing all odd/even indexed pairs of adjacent elements in the list and swapping pairs where in the wrong order (where the first is larger than the second). The next step repeats this for even/odd indexed pairs (of adjacent elements). Then it alternates between odd/even and even/odd steps until the list is sorted.

Sorting on processor arrays

On parallel processors, with one value per processor and only local left–right neighbor connections, the processors all concurrently do a compare–exchange operation with their neighbors, alternating between odd–even and even–odd pairings. This algorithm was originally presented, and shown to be efficient on such processors, by Habermann in 1972.

The algorithm extends efficiently to the case of multiple items per processor. In the Baudet–Stevenson odd–even merge-splitting algorithm, each processor sorts its own sublist at each step, using any efficient sort algorithm, and then performs a merge splitting, or transposition–merge, operation with its neighbor, with neighbor pairing alternating between odd–even and even–odd on each step.

Batcher's odd–even mergesort

A related but more efficient sort algorithm is the Batcher odd–even mergesort, using compare–exchange operations and perfect-shuffle operations.

Batcher's method is efficient on parallel processors with long-range connections.

Proof of correctness

Claim: Let a₁,...,aₙ be a sequence of data ordered by <. The odd–even sort algorithm correctly sorts this data in n passes. (A pass here is defined to be a full sequence of odd–even, or even–odd comparisons. The passes occur in order pass 1: odd–even, pass 2: even–odd, etc.)

Proof:

This proof is based loosely on one by Thomas Worsch.

Since the sorting algorithm only involves comparison-swap operations and is oblivious (the order of comparison-swap operations does not depend on the data), by Knuth's 0–1 sorting principle, it suffices to check correctness when each aᵢ is either 0 or 1. Assume that there are e 1s.

Observe that the rightmost 1 can be either in an even or odd position, so it might not be moved by the first odd–even pass. But after the first odd–even pass, the rightmost 1 will be in an even position. It follows that it will be moved to the right by all remaining passes. Since the rightmost one starts in position greater than or equal to e, it must be moved at most n-e steps. It follows that it takes at most n-e+1 passes to move the rightmost 1 to its correct position.

Now, consider the second rightmost 1. After two passes, the 1 to its right will have moved right by at least one step. It follows that, for all remaining passes, we can view the second rightmost 1 as the rightmost 1. The second rightmost 1 starts in position at least e-1 and must be moved to position at most n-1, so it must be moved at most (n-1)-(e-1)=n-e steps. After at most 2 passes, the rightmost 1 will have already moved, so the entry to the right of the second rightmost 1 will be 0. Hence, for all passes after the first two, the second rightmost 1 will move to the right. It thus takes at most n-e+2 passes to move the second rightmost 1 to its correct position.

Continuing in this manner, by induction it can be shown that the i -th rightmost 1 is moved to its correct position in at most n-e+i passes. Since i≤ e, it follows that the i -th rightmost 1 is moved to its correct position in at most n-e+e=n passes. The list is thus correctly sorted in n passes. QED.

We remark that each pass takes O(n) steps, so this algorithm has O(n²) complexity.