Radix Sort

How It Works

Radix sort orders integers by processing one digit position at a time, least significant first, using a stable sort — almost always counting sort — for each pass. Stability is the linchpin: when the pass for digit d finishes, ties on digit d retain the order established by all lower digits, so after the final, most significant pass the array is fully sorted.

With d digit positions and base k, the cost is O(d * (n + k)); choosing base 256 makes d small (four passes for 32-bit values) while keeping the per-pass count array tiny. For bounded-size integers d is a constant, so radix sort is effectively linear — beating comparison sorts asymptotically — at the price of O(n + k) auxiliary space and integer-like keys only. The MSD variant recurses from the most significant digit instead and suits variable-length strings.

Step-by-Step Visualization

Code

static int[] radixSort(int[] arr) {
  int max = 0;
  for (int x : arr) max = Math.max(max, x);
  int[] result = arr.clone();
  for (int exp = 1; max / exp > 0; exp *= 10) {
    List<List<Integer>> buckets = new ArrayList<>();
    for (int i = 0; i < 10; i++) buckets.add(new ArrayList<>());
    for (int num : result) buckets.get((num / exp) % 10).add(num);
    int idx = 0;
    for (List<Integer> bucket : buckets)
      for (int num : bucket) result[idx++] = num;
  }
  return result;
}

Tips & Gotchas

Practice Problems

• 1Maximum Gap
• 2Sort an Array
• 3Query Kth Smallest Trimmed Number

About the Linear-Time Sorts Pattern

These bypass the O(n log n) barrier by NOT comparing elements. Instead, they use the values directly. The catch: they only work when values fall within a known, bounded range.

Common Sorting Interview Problems

• Sort Colors
• Kth Largest Element
• Merge Intervals
• Largest Number
• Sort List
• Meeting Rooms

Frequently Asked Questions

Other Linear-Time Sorts Techniques