I've been experimenting with a sorting visualizer and bitonic sort is confusing me. With an array of 1,566 elements, entering the values in reverse order produces no obvious lasting changes until roughly 31,573 comparisons. With an array that starts already sorted, noticeable changes also seem to wait until around 30,000 comparisons. Why does bitonic sort behave this way, and what is it doing during those early comparisons?
3 Answers
Each stage merges pairs of runs in opposite directions: one ascending and the other descending. The result is a larger run that rises and then falls, which can still look disordered. The process repeats with increasingly large runs until the final merge turns the whole array into ascending order. With an already sorted or reverse-sorted input, the comparison network still performs essentially the same scheduled operations, so the visual behavior is not input-adaptive.
Bitonic sort is mainly designed for parallel hardware such as GPUs, where having a fixed sequence of comparisons is useful. On a single processor it can look unnecessarily inefficient, because it performs its comparison network regardless of whether the input is already sorted. Also, classic bitonic sort works most naturally with a power-of-two number of elements; a visualizer may pad a non-power-of-two array or handle the extra elements specially.
Bitonic sort does not improve the array one small step at a time like bubble sort. It first constructs sequences that alternate between ascending and descending sections. The early comparisons are preparing those bitonic sequences, so many swaps are temporary or not visually meaningful. Once the larger merge stages begin, the pieces finally combine into one sorted sequence, which is why the result can appear to happen all at once.
That makes sense—so the early work is building the structure needed by the later merge stages rather than directly moving values toward their final positions.