How LSD Radix Sort Works

The LSD variant processes digits from right to left. For each digit position, elements are grouped into buckets 0–9 based on that digit, then collected back maintaining order. This repeats for every digit in the largest number.

Stability is critical — when two numbers share the same digit at the current position, their relative order from the previous pass is preserved. This ensures correctness after all passes.

void radixSort(int arr[], int n) {
  int max = *max_element(arr, arr + n);
  for (int exp = 1; max / exp > 0; exp *= 10)
    countingSort(arr, n, exp);
}

void countingSort(int arr[], int n, int exp) {
  int output[n], count[10] = {0};
  for (int i = 0; i < n; i++) count[(arr[i] / exp) % 10]++;
  for (int i = 1; i < 10; i++) count[i] += count[i - 1];
  for (int i = n - 1; i >= 0; i--) {
    output[count[(arr[i] / exp) % 10] - 1] = arr[i];
    count[(arr[i] / exp) % 10]--;
  }
  for (int i = 0; i < n; i++) arr[i] = output[i];
}

Time and Space Complexity

Radix Sort runs in O(d × n) time and uses O(n + k) auxiliary space, where k is the radix (10 for decimal). When d is constant, this is effectively linear. However, it is not suitable for floating-point numbers or negative values without modification.

// Java: Radix Sort for strings (variable length)
static void radixSortString(String[] arr, int maxLen) {
  for (int pos = maxLen - 1; pos >= 0; pos--) {
    int n = arr.length;
    String[] output = new String[n];
    int[] count = new int[256];
    for (String s : arr)
      count[pos < s.length() ? s.charAt(pos) : 0]++;
    for (int i = 1; i < 256; i++) count[i] += count[i - 1];
    for (int i = n - 1; i >= 0; i--) {
      int idx = pos < arr[i].length() ? arr[i].charAt(pos) : 0;
      output[count[idx] - 1] = arr[i];
      count[idx]--;
    }
    System.arraycopy(output, 0, arr, 0, n);
  }
}