Sort elements based on value of a single digits in each pass.

Radix ( or base ) is the number of digits used to represent a number, for e.g. decimal system uses 10 digits $(0..9)$, binary uses 2 digits $(0,1)$.

Radix sort does NOT use comaprison for sorting, hence it can be faster than comparison sorts which are speed limited to $O(n log(n))$ on the speed.
It can run as fast as $O(n+k)$ time.
It can be used to sort strings when they are represented as integers.

General idea

radixSort (array):
    for digit -> 0 to numberOfDigits:
        stableSort(array, digit)

LSD sort : Least Significant Digit

• Each number should have the same number of digits (width).

lsdRadixSort(array):
    for lsd -> digits to 0: //lsd -> msd
        countingSort(array, lsd)

countinsSort(array, digit):
  //TODO

MSD sort : Most significant Digit

MSDsort(array, 0, array.length, 0)

MSDsort(array, subArrStart, subArrEnd, msd):
  count = countingSort(array, msd)
  for i->0 to maxWidth //radix
     MSDsort(array, count[i], count[i+1], i+1)

Running time

Best case

MSD radix : Points to note

• Large number of small subarrays
• When all the strings/number are the same
• Counting sort uses extra space since it uses a count array and an aux array, this can be eliminated if we sacrifice stability

In Books

• Algorithms, 4th Edition, Sedgewick, Chapter 5.1, "MSD String Sort"

References

Brilliant Radix Sort MIT OCW lecture notes