I've been experimenting with a sorting visualizer and I'm having trouble understanding bitonic sort. With an array of 1,566 elements, entering the values in reverse order produces no obvious lasting changes until roughly 31,573 comparisons. Using an array that's already sorted gives a similar result, with visible progress only appearing after about 30,000 comparisons. Why does bitonic sort behave this way?
3 Answers
Bitonic sort doesn't sort the array incrementally the way bubble sort does. It first builds bitonic sequences—runs that increase and then decrease—by repeatedly comparing pairs in opposite directions. Those early comparisons are mostly establishing the structure, so the array may look unchanged even though useful work is happening. The later merge stages combine those sequences until the entire array becomes sorted. It also performs a predictable sequence of comparisons regardless of the input, which is useful for parallel hardware and GPUs.
The visualizer is showing the main oddity of bitonic sort: it repeatedly merges runs in opposite directions, with one part ascending and the other descending. Each stage creates larger bitonic sequences, but those sequences won't necessarily resemble the final sorted array. Only near the final merge stages do the elements settle into globally sorted order.
Bitonic sort is mainly designed for parallel execution, such as on a GPU or sorting network. On a single processor it can look inefficient because it performs the same comparison pattern even when the input is already sorted or reversed. That fixed pattern explains why both inputs appear to wait until roughly the same point before showing obvious changes.
That makes sense—so the early comparisons are preparing the bitonic runs rather than producing a visibly sorted prefix.