Bucket Sort
- Ω( n + k )
- Θ( n + k )
- O( n2 )
- space O( n + k )
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 bucket sort works
Bucket sort spreads the elements over a number of buckets by value range, sorts each bucket with insertion sort, and reads the buckets back in order.
Read more
The only comparisons outside the buckets are the n-1 needed to find the largest value. Placing an element into a bucket is arithmetic on its value, not a comparison, and the buckets live in an auxiliary buffer, so most of the work appears as Reads and Writes. It is fast when the values are spread evenly and slow when most land in one bucket.
| Best time | Ω( n + k ) | good |
|---|---|---|
| Average time | Θ( n + k ) | good |
| Worst time | O( n2 ) | poor |
| Worst space | O( n + k ) | fair |
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.