What is Radix sort

What's the origin of Radix sort?

Founded by Herman Hollerith in 1887 while inventing a tabulating machine for punched cards. The innovation led to the founding of renown computer company: International Business Machines (IBM).

What is it?

A non-comparative, digit-based sorting algorithm that sorts numbers digit by digit, starting from the least significant digit (LSD) to the most significant. O(n*k), where n is the number of elements and k is the number of digits in the largest number. It is useful for sorting numbers, especially when the number of digits is small relative to the number of elements.

What are the real world applications?

When sorting a large list of integers with fixed length like phone numbers, normalized data, and IP addresses. Why fixed in length? Because it's performance is predictable in this scenario. The d variable in the time complexity will be constant in this scenario providing an optimal linear solution.

Example:

Let us demonstrate with the following unordered list of integers: [65, 35, 456, 4, 89, 23, 86, 117, 0]

One's

[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}]

Psuedocode:

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

Difficulty (1-5)

Four because it's not intuitive. However the short code makes it easier to digest.