suryapolina.com

Radix sort is used to sort numbers in a list using their respective digits. Sorting a fixed length list of phone numbers, data, or IP addresses could use radix sort. Why fixed length? Because only then can we have linear performance (standard). Below is an example run through of the logic.

List of integers:

[65, 35, 456, 4, 89, 23, 86, 117, 0]

One's Digit

[65, 35, 456, 4, 89, 23, 86, 117, 0] ----> [{0}, {23}, {4}, {65, 35}, {456}, {86}, {117}]

Ten's

[0, 23, 4, 65, 35, 456, 86, 117] ----> [{00,04}, {117}, {23}, {35}, {456}, {65}, {86}]

Hundred's

[0, 4, 117, 23, 35, 456, 65, 86]. ----> [{000,004, 023, 035, 065, 086}, {117}, {456}]

RadixSort(arr):
  maxNumber = findMaxNumber(arr)
  digitPlace = 1
  while maxNumber / digitPlace > 0:
	CountingSortByDigit(arr, digitPlace)
	digitPlace = digitPlace * 10

CountingSortByDigit(arr, digitPlace):
  count = array of size 10, initialized to 0
  output = array of same size as arr
  for each element in arr:
    digit = (element / digitPlace) % 10
    count[digit] = count[digit] + 1
  for i = 1 to 9:
    count[i] = count[i] + count[i-1]
  for i from end of arr to 0:
    digit = (arr[i] / digitPlace) % 10
    output[count[digit] - 1] = arr[i]
    count[digit] = count[digit] - 1
  for i from 0 to end of arr:
    arr[i] = output[i]
      
  findMax(arr):
    max = arr[0]
    for each element in arr:
      if element > max:
        max = element
    return max

Time:

O(n*d) where n is the length of the input and d is the size of the largest available integer

Space:

O(n) where n is the length of the input

Radix Sort