Distribution Sorts

Radix & Bucket Sort

Non-comparison based sorting algorithms achieving linear complexity under value constraints.

What is Radix & Bucket Sort?

Radix Sort and Bucket Sort are non-comparison based sorting algorithms. Radix Sort processes numbers digit-by-digit, from the least significant digit (LSD) to the most significant digit (MSD), using Counting Sort as a stable sorting subroutine. Bucket Sort partitions elements into a finite number of buckets, sorts each bucket individually (e.g. using Insertion Sort), and concatenates them.

Key Characteristics:

  • Does not compare elements directly.
  • Radix Sort is stable.
  • Bucket Sort relies on uniform distribution of inputs.
  • Can sort in O(N) linear time under specific conditions.

Complexity Analysis

Avg Time Complexity: O(d * (N + k)) for Radix, O(N + k) average for Bucket
Space Complexity: O(N + k) auxiliary memory space
Best Case: O(N)
Worst Case: O(N^2) for Bucket Sort (skewed buckets)

How it Works Step-by-Step

  1. Radix Sort: Find the maximum number to determine the number of digits (d).
  2. Counting Sort Pass: Loop from least significant digit (1s) to most significant digit (10s, 100s, ...).
  3. Evaluate Digit: Perform stable Counting Sort on the array based on the active digit.
  4. Bucket Sort: Create an array of empty buckets.
  5. Distribute: Put array elements into buckets based on value range: index = floor(N * value / Max).
  6. Sort & Merge: Sort each bucket individually and concatenate results.

Code Implementation

Worked Trace Example

Radix sorting [170, 45, 75, 90, 802, 24, 2, 66]:
1. Sort by 1s digit: [170, 90, 802, 2, 24, 45, 75, 66]
2. Sort by 10s digit: [802, 2, 24, 45, 66, 170, 75, 90]
3. Sort by 100s digit: [2, 24, 45, 66, 75, 90, 170, 802]
Result: Sorted array.

Ready to Understand Radix & Bucket Sort Visually?

Don't just read about it. Launch our interactive, premium algorithm visualizer to step through calculations in real-time.

Launch Radix & Bucket Sort Visualizer →