Radix Sort
- Ω( d(n + b) )
- Θ( d(n + b) )
- O( d(n + b) )
- space O( n + b )
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 radix sort works
Radix sort (least significant digit first, base 10) sorts the numbers one decimal digit at a time, starting with the ones digit. Each pass is a stable counting sort on that digit, so after the last pass the whole array is in order.
Read more
The only comparisons are the n-1 needed to find the largest value, which tells it how many digits to process. Placing elements is done by indexing into count and output buffers, which show up as Reads and Writes instead. It does one pass per digit, so it is linear in n for numbers with a bounded number of digits.
| Best time | Ω( d(n + b) ) | good |
|---|---|---|
| Average time | Θ( d(n + b) ) | good |
| Worst time | O( d(n + b) ) | good |
| Worst space | O( n + b ) | 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.