Overview

Radix sort's purpose is to sort items in an array using the place value system as the means of sort. Real world use cases include sorting an array of phone numbers, or IP addresses. It's important to note that the elements in the array must consist of the same data type, for example, all phone numbers in the array must contain the same 10 digit pattern (USA), otherwise the logic will need to account for variable data lengths.

Example:

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

First loop: 1's place

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

Second: 10's

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

Third: 100's

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

Done!

Pseudocode:

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

sortByDigit(arr, place):
  count = array of size 10, initialized to 0
  output = array of same size as arr
  for each element in arr:
    digit = (element / place) % 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] / place) % 10
    output[count[digit] - 1] = arr[i]
    count[digit] = count[digit] - 1
  for i from 0 to end of arr:
    arr[i] = output[i]
      
  findMaxNumber(arr):
    max = arr[0]
    for each element in arr:
      if element > max:
        max = element
    return max

Complexity:

Time:

• O(N*D); N is the size of the input array and D is the size of the largest/longest existing data point.

Space:

• O(N); N is the size of the input.