| Class: | Sorting algorithm |
| Data: | Array |
| Time: | O(n2) |
| Best-Time: | O(n) |
| Space: | O(1) |
| Optimal: | No |
In computing, an odd–even sort or odd–even transposition sort (also known as brick sort[1] 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, if a pair is in the wrong order (the first is larger than the second) the elements are switched. 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.
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.[2]
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.
A related but more efficient sort algorithm is the Batcher odd–even mergesort, using compare–exchange operations and perfect-shuffle operations.[3] Batcher's method is efficient on parallel processors with long-range connections.[4]
The single-processor algorithm, like bubblesort, is simple but not very efficient. Here a zero-based index is assumed:
Claim: Let
a1,...,an
n
Proof:
This proof is based loosely on one by Thomas Worsch.[5]
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,[6] [7] it suffices to check correctness when each
ai
e
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
n-e
n-e+1
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
n-1
(n-1)-(e-1)=n-e
n-e+2
Continuing in this manner, by induction it can be shown that the
i
n-e+i
i\leqe
i
n-e+e=n
n
We remark that each pass takes
O(n)
O(n2)