Bitonic Sort Visualization
Bitonic Sort builds rising-then-falling sequences and merges them with a fixed network of comparisons.
How it works
Bitonic Sort is a sorting network: the sequence of comparisons is fixed in advance and doesn't depend on the data. It builds bitonic sequences (ones that rise and then fall), then repeatedly compares elements half a block apart to split them into two smaller bitonic halves, until everything is sorted. It needs the size to be a power of two.
It does n log² n comparisons, more than Merge Sort, but every comparison in a stage is independent, so it runs extremely well on parallel hardware like GPUs. It is not stable.
What to watch for
Watch symmetric patterns appear: blocks sort up and down alternately, then merge in regular, repeating sweeps.
Complexity
- Best
- n log² n
- Average
- n log² n
- Worst
- n log² n
- Extra space
- 1
- Stable
- No
Race it
Same shuffle, same speed, one winner: Bitonic vs Merge. Or open the studio to try other layouts, sizes and speeds, and make a video of it.
FAQ
Why does Bitonic Sort need a power of two?
Its network halves blocks at every step. Other sizes need padding.
Where is Bitonic Sort used?
On GPUs and in hardware sorting networks, where all comparisons in a stage run at the same time.