Batcher's odd-even merge sort divides elements into odd and even indexed groups, recursively sorts them, then merges using an odd-even merge network. It has the same asymptotic complexity as bitonic sort but with a different structure.
Properties
| Property | Value |
|---|---|
| Depth (stages) | O(log2 n) |
| Comparators | O(n log2 n) |
| Parallelism | Up to n/2 comparisons per stage |
| Best for | Power-of-2 sizes, understanding merging |