RadixSort

Radix sort is a non-comparative sorting algorithm. It avoids comparison by creating and distributing elements into buckets according to their radix. For elements with more than one significant digit, this bucketing process is repeated for each digit, while preserving the ordering of the prior step, until all digits have been considered. For this reason, radix sort has also been called bucket sort and digital sort.

Radix sort can be applied to data that can be sorted lexicographically, be they integers, words, punch cards, playing cards, or the mail. Wikipedia (opens new window)

Complexity and performance

Radix sorts operates in O(nw) time, where n is the number of keys, and w is the key length. LSD variants can achieve a lower bound for w of 'average key length' when splitting variable length keys into groups as discussed above.

Optimized radix sorts can be very fast when working in a domain that suits them. They are constrained to lexicographic data, but for many practical applications this is not a limitation. Large key sizes can hinder LSD implementations when the induced number of passes becomes the bottleneck. Wikipedia (opens new window)

Legend

• The circle shows the current column in sorting.
• The current Key(s) in sorting, is/are green.
• The sorted columns are dark-green.