Speed:

Radix Sort

Time: O(d × (n + k))Space: O(n + k)Stable & Non-comparison

🔢How Radix Sort Works

Radix Sort is a non-comparison based sorting algorithm that sorts integers by processing individual digits. It works by sorting the numbers digit by digit, starting from the least significant digit (rightmost) to the most significant digit (leftmost).

The key insight is to use a stable sorting algorithm (like counting sort) for each digit position:

Find maximum: Determine the number of digits needed
Process digits: Sort by each digit position using counting sort
Maintain stability: Preserve relative order of equal elements
Linear time: Achieves O(d×(n+k)) where d is digit count

💻Implementation

// Radix Sort Implementation (for non-negative integers)
function radixSort(arr) {
  if (arr.length === 0) return arr;
  
  // Find the maximum number to know number of digits
  const max = Math.max(...arr);
  
  // Do counting sort for every digit
  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
    countingSortByDigit(arr, exp);
  }
  
  return arr;
}

function countingSortByDigit(arr, exp) {
  const n = arr.length;
  const output = new Array(n);
  const count = new Array(10).fill(0);
  
  // Store count of occurrences of each digit
  for (let i = 0; i < n; i++) {
    const digit = Math.floor(arr[i] / exp) % 10;
    count[digit]++;
  }
  
  // Change count[i] so it contains actual position of digit in output
  for (let i = 1; i < 10; i++) {
    count[i] += count[i - 1];
  }
  
  // Build the output array
  for (let i = n - 1; i >= 0; i--) {
    const digit = Math.floor(arr[i] / exp) % 10;
    output[count[digit] - 1] = arr[i];
    count[digit]--;
  }
  
  // Copy the output array to arr
  for (let i = 0; i < n; i++) {
    arr[i] = output[i];
  }
}

// Alternative LSD (Least Significant Digit) implementation
function radixSortLSD(arr, base = 10) {
  if (arr.length === 0) return arr;
  
  const max = Math.max(...arr);
  const maxDigits = Math.floor(Math.log(max) / Math.log(base)) + 1;
  
  for (let digit = 0; digit < maxDigits; digit++) {
    const buckets = Array.from({ length: base }, () => []);
    
    for (let num of arr) {
      const digitValue = Math.floor(num / Math.pow(base, digit)) % base;
      buckets[digitValue].push(num);
    }
    
    arr = [].concat(...buckets);
  }
  
  return arr;
}

📊Algorithm Analysis

Time Complexity

• Best/Average/Worst: O(d × (n + k))
• d: number of digits
• n: number of elements
• k: range of digits (usually 10)

Key Properties

• Non-comparison based: doesn't compare elements
• Stable: maintains relative order
• Linear time: when d is constant
• External sorting: works well with large data

🔄 Radix Sort Variants

• LSD (Least Significant Digit): Start from rightmost digit
• MSD (Most Significant Digit): Start from leftmost digit
• Binary radix sort: Base-2 for binary data
• String radix sort: For lexicographic ordering

🎯 Best Use Cases

• Integer sorting: Fixed-width integers
• String sorting: Fixed-length strings
• Database indexing: Numeric keys
• External sorting: Large datasets on disk