Comb Sort
- Ω( n log n )
- Θ( n2 )
- O( n2 )
- space O( 1 )
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 comb sort works
Comb sort improves bubble sort by comparing elements that are far apart. It starts with a gap of about the array length and shrinks the gap by a factor of 1.3 after every pass, finishing with a gap of 1, which is a plain bubble pass.
Read more
Moving small values near the end (the "turtles" that slow bubble sort down) long distances in a single swap removes most inversions early. The final bubble passes then have little left to do.
| Best time | Ω( n log n ) | good |
|---|---|---|
| Average time | Θ( n2 ) | poor |
| Worst time | O( n2 ) | poor |
| Worst space | O( 1 ) | 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.