Bitonic Sort
- Ω( n log2 n )
- Θ( n log2 n )
- O( n log2 n )
- space O( log n )
Array
Comparator strip
Index down, time to the right
- Comparisons count only element-against-element checks; loop and index checks are never counted.
- Reads and writes include reads and writes to helper buffers (merge, counting, radix, bucket and tim sort).
- A swap counts once, as a swap. It is never also counted as a read or a write.
- Real time is the average time of the counted sort on this device over repeated runs, measured once before playback and independent of animation speed. Visual time is the time spent animating, excluding pauses.
How bitonic sort works
Bitonic sort is a sorting network: the sequence of compare-and-swap operations is fixed in advance and does not depend on the data. It sorts the two halves in opposite directions to build a bitonic sequence, then merges it with a cascade of compare-exchanges.
Read more
Because the comparisons are data independent, many of them can run in parallel, which is why it is popular on GPUs. Run sequentially it does O(n log² n) comparisons. This version also handles array sizes that are not a power of two.
| Best time | Ω( n log2 n ) | fair |
|---|---|---|
| Average time | Θ( n log2 n ) | fair |
| Worst time | O( n log2 n ) | fair |
| Worst space | O( log n ) | good |
Big O notation gives the lower, average and upper bounds of an algorithm. Time complexity bounds the number of operations; space complexity bounds the extra memory it uses.