Odd-Even Sort
Alternates comparing all odd-indexed pairs then all even-indexed pairs. Each phase is independent, so it parallelizes trivially.
- Category
- Sorting
- Time complexity
- O(n²)
- Space complexity
- O(1)
Pseudocode
repeat until sorted odd phase: compare (1,2),(3,4)… even phase: compare (0,1),(2,3)… swap out-of-order pairs
Reference implementation
while not sorted:
for start in (1, 0):
for i in range(start, n-1, 2):
if a[i] > a[i+1]: swap