Bitonic Sort vs Merge Sort
Same 128 values, same shuffle, same speed. Merge Sort finishes first and turns gold: 1,627 operations to 2,668.
The numbers
- Bitonic operations
- 2,668
- Merge operations
- 1,627
- Bitonic average
- n log² n
- Merge average
- n log n
- Bitonic worst
- n log² n
- Merge worst
- n log n
Bitonic Sort
Bitonic Sort builds rising-then-falling sequences and merges them with a fixed network of comparisons. More on Bitonic Sort.
Merge Sort
Merge Sort splits the list in half, sorts both halves, then merges the two sorted halves into one. More on Merge Sort.
FAQ
Which is faster, Bitonic Sort or Merge Sort?
On this shuffle of 128 values, Merge Sort needed 1,627 operations and Bitonic Sort needed 2,668, about 1.6× as many. On average Bitonic Sort is n log² n and Merge Sort is n log n.
Which one is stable?
Merge Sort is stable; Bitonic Sort is not.
How is the race fair?
Both algorithms start from the same shuffle and run the same number of operations per frame. Every comparison, swap and write counts as one operation, so the one that needs fewer operations finishes first.