When does Radix Sort beat Quick Sort?

Under what dataset conditions does Radix Sort outperform comparison sorters?

Searching & Sorting AlgorithmsIntermediate LevelStudy Time: 22 mins

Radix Sort Algorithm

Radix Sort is a non-comparative sorting algorithm that sorts integers digit-by-digit from least significant digit (LSD) to most significant digit (MSD) using counting sort buckets.

Radix Sort Visualizer

Array loaded. Trigger Radix Sort to distribute elements into digit buckets (0-9).

Current Array State

170[0]

45[1]

75[2]

90[3]

802[4]

24[5]

2[6]

66[7]

Decimal Buckets (0 - 9)

Bin 0

Bin 1

Bin 2

Bin 3

Bin 4

Bin 5

Bin 6

Bin 7

Bin 8

Bin 9

Speed:

Radix Sort Digit Bucket Trace

Sample Input:Input Array: [170, 45, 75, 90, 802, 24, 2, 66]

Step 1

Sort by 1s Digit Place

Group numbers into digit buckets [0..9] based on the least significant digit (1s place).

1s Digits: [170, 90], [802, 2], [24], [45, 75], [66] -> Output: [170, 90, 802, 2, 24, 45, 75, 66]

Preserves stable relative order of equal 1s digits.

Step 2

Sort by 10s Digit Place

Group numbers into digit buckets [0..9] based on the 10s digit place.

10s Digits: [802, 2], [24], [45], [66], [170, 75], [90] -> Output: [802, 2, 24, 45, 66, 170, 75, 90]

Maintains stability across digit passes.

Step 3

Sort by 100s Digit Place

Group numbers into digit buckets [0..9] based on the 100s digit place.

100s Digits: [2, 24, 45, 66, 75, 90], [170], [802] -> Sorted: [2, 24, 45, 66, 75, 90, 170, 802]

Achieves sorted output in O(d × N) without single key comparison!

Real-world analogy: Sorting Date Records

Digit Buckets

Hover over items for details

Sort mail by day first (01-31), then sort by month (01-12), then sort by year. The final stack will be completely ordered by date.

Digit Buckets= 10 buckets (0-9) sorting numbers by active digit place.

Complexity analysis

Scenario Simulator: Dataset Size (N = 500)

Presets:

N = 10N = 10,000

Complexity Curve MapRadix Sort: O(N) Linear Time

Hover curves to inspect classes

Time Steps (N=500)

500 steps (Linear)

O(N) Linear Time

Space Footprint

O(N) Memory

Memory growth rate as N expands.

Performance Rank

Efficient Tier

Relative efficiency rating for large N.

Operation	Time Complexity	Space Complexity
Time Complexity	O(d × (N + k))	O(N + k)

Code implementations

function radixSort(arr) {
  const maxNum = Math.max(...arr);
  let exp = 1;
  while (Math.floor(maxNum / exp) > 0) {
    countingSortByDigit(arr, exp);
    exp *= 10;
  }
  return arr;
}