Odd-Even Sort

What is odd-even sort?

Odd-even sort, also called brick sort, is a cousin of bubble sort. Instead of walking across the list one pair at a time, it works in two alternating phases.

In the even phase it checks the pairs (0, 1), (2, 3), (4, 5) and so on. In the odd phase it checks the pairs (1, 2), (3, 4), (5, 6). Each pair gets swapped if it is out of order. It keeps alternating until a full round makes no swaps.

Draw the pairs row by row and they overlap like bricks in a wall. That is where the other name comes from.

How it works, step by step

Press play above. Blue bars are being compared, orange bars are being swapped. Notice how the compares hop across the list two steps at a time.

1. Set done = True. Assume the list is sorted until a swap proves otherwise.
2. Even phase: for i = 0, 2, 4, …, compare a[i] and a[i + 1]. Swap if the left one is bigger, and set done = False.
3. Odd phase: do the same for i = 1, 3, 5, ….
4. If done is still true after both phases, stop. Otherwise, go back to step 1.

In the code, for s in (0, 1) runs the two phases, and range(s, n - 1, 2) steps through every other pair. The pairs in one phase never share a value, which is the whole point, as the next section explains.

Built for parallel hardware

Look at the even phase: (0, 1), (2, 3), (4, 5). No two pairs touch the same position. That means all of them could be checked at the same time, by different processors, without getting in each other’s way.

That is why odd-even sort shows up in parallel computing and in sorting networks built into hardware. With one processor per pair, each phase takes one time step, and at most n phases sort any list. So with enough processors it runs in O(n) time.

On a normal computer, one step at a time, that advantage disappears.

Time and space complexity

Each round (one even phase plus one odd phase) makes about n − 1 comparisons. The sort needs at most n rounds.

Best case, O(n): the list is already sorted. The first round finds nothing to swap, and the sort stops.

Worst case, O(n²): a value can move at most one place per phase, so a value that belongs at the other end needs about n phases to get there. For example, the smallest value sitting at the end of the list. Try the “reversed” preset.

Average case, O(n²): up to n rounds of about n comparisons.

Space is O(1). It sorts in place with a flag and an index.

Common mistakes

• Stopping after an even phase with no swaps. You need a full round (both phases) with no swaps before the list is sorted.
• Letting i run to n - 1 on the odd phase. The last pair starts at n - 2, so the range must stop at n - 1 (exclusive).
• Mixing up “odd” and “even”. Some sources name the phases by the second index. It doesn’t matter which comes first, as long as they alternate.

When to use it

Use it when you really have parallel hardware, like a GPU or an array of simple processors, and want a sort that is short and easy to split up.

On a normal CPU, insertion sort is faster among the simple sorts, and your language’s built-in sort is faster than both. Odd-even sort is still worth knowing as a first taste of how parallel algorithms are designed: find work that doesn’t overlap, and do it all at once.

Questions

Is odd-even sort stable?

Yes. It only swaps neighbors when the left one is strictly bigger, so equal values keep their order.

Why is it called brick sort?

The even pairs and odd pairs overlap like rows of bricks in a wall.

Is odd-even sort faster than bubble sort?

On one processor, not really: both are O(n²). With many processors it can run in O(n) time, which bubble sort cannot.