Radix sort

Radix sort is a fast sort algorithm which can be used to sort items that are identified by unique keys. Every key is a string or number, and radix sort sorts these keys in a particular lexicographic-like order. The algorithm operates in O(nk) time, where n is the number of items, and k is the average key length. This algorithm was orignally used to sort [punched card]?s in several passes.

Radix sort has resurfaced as an alternative to other high performance sorting algorithms (like quicksort, heapsort and merge sort) which require O(n lg n)) comparisons, where n is the number of items to be sorted. These other algorithms are able to sort with respect to more complicated orderings than lexicographic, but this is of little importance in many practical applications.

If the size of the possible key space is proportional to the number of items, then each key will be lg n symbols long, and radix sort uses O(n lg n)) time in this case.

The greatest disadvantages or radix sort are that it usually cannot be made to run in place, so O(n) additional memory space is needed, and that it requires one pass for each symbol of the key, so it is very slow for potentially-long keys.

Radix sort uses the following sorting order: short keys come before longer keys, and keys of the same length are sorted lexicographically. This coincides with the normal order of numbers, if the numbers are represented as digit strings.

A radix sort algorithm works as follows:

1. take the least significant digit (or group bits) of each key.
2. sort the list of elements based on that digit, but keep the order of elements with the same digit (this is the definition of a stable sort).
3. repeat the sort with each more significant digit.

The sort in step 2 is usually done using [bucket sort]?, which works since there are only finitely many digits.

An example

Sort the list:
170, 45, 75, 90, 2, 24, 802, 66

1. sorting by least significant digit (1s place) gives:
   170, 90, 2, 802, 24, 45, 75, 65
2. sorting by next digit (10s place) gives:
   2, 802, 24, 45, 67, 170, 75, 90
3. sorting by most significant digit (100s place) gives:
   2, 24, 45, 65, 75, 90, 170, 802

Recursion

A recursively subdividing radix sort algorithm works as follows:

1. take the most significant digit (or group bits) of each key.
2. sort the list of elements based on that digit, grouping elements with the same digit into one "bucket".
3. recursively sort each bucket, starting with the next most significant digit.
4. concatentate the buckets together in order

This recursive method can be interpreted as a generalization of quicksort from strings with two possible symbols to strings with any number of possible symbols.

External link:

[Demonstration and comparison] of Radix sort with Bubble sort, Merge sort and Quicksort implemented in JavaScript

---

/Talk