Description and implementation of a radix sort algorithm.

radix-sort.js

/**
 * Radix Sort: Radix (or base) means: "the base of a
 * system of numeration." Radix sorts by analyzing the
 * place values of each number. Each number must be a
 * whole number, or positive integer. Radix sort can be used
 * with a variety of base values, though here I focus
 * only on our decimal base 10 system.
 *
 * Process:
 * Create an auxiliary array with a length of ten (one
 * element for each unique digit in base 10). Place values
 * from the unsorted array into the auxiliary array
 * according to their place value. For example: the number
 * 5 would be sorted into the 6th element of the
 * auxiliary array. Once all the values are contained by
 * the auxiliary array, refill the original unsorted array
 * with the sorted values in the order they appear in the
 * auxiliary array. Address the visualization for
 * clarification. Repeat this process up until the largest
 * place value of the array has been sorted.
 *
 * Performance:
 * n = elements in array
 * k = number of place values in array's largest value
 * Best Time Complexity: O(nk)
 * Average Time Complexity: O(nk)
 * Worst Time Complexity: O(nk)
 * Space Complexity: O(n+k)
 *
 * Visualization: (Select rad at the top of the page) https://visualgo.net/en/sorting
 */

function radixSort (array) {
  const digits = maxDigits(array)
  for (let digit = 0; digit < digits; digit++) {
    // Create auxiliary array with length equal to quantity
    // of unique digits in base (10 in decimal system).
    // Initialize each element to an empty array.
    const auxiliaryArray = Array.from({length: 10}, () => [])
    // Insert values into auxiliary array according to
    // their place value.
    for (let i = 0; i < array.length; i++) {
      const value = array[i]
      const placeVal = placeValue(value, digit)
      auxiliaryArray[placeVal].push(value)
    }
    // Empty values from auxiliary array, in order
    let insertionIndex = 0
    auxiliaryArray.forEach(digitArray => {
      digitArray.forEach(value => {
        array[insertionIndex] = value
        insertionIndex++
      })
    })
  }
  return array
}

// Returns max number of digits of any number in the array.
function maxDigits (array) {
  let maxDigits = 0
  for (let i = 0; i < array.length; i++) {
    maxDigits = Math.max(maxDigits, digitQuantity(array[i]))
  }
  return maxDigits
}

// Returns quantity of digits within a number.
function digitQuantity (number) {
  return number.toString().length
}

// Returns the place value of a number.
function placeValue (number, place) {
  const divisor = 10 ** place
  return Math.floor((number / divisor) % 10)
}

const data = Array.from(
  {length: 10},
  () => Math.floor(Math.random() * 100)
)

console.log('Unsorted:')
console.log(data)
console.log('Sorted:')
radixSort(data)
console.log(data)