Radix Sort

Digit-by-digit distribution sorting

Radix Sort sorts numbers by processing individual digits. By using a stable sorting subroutine (like Counting Sort) for each digit, it avoids comparisons and achieves linear time complexity for fixed-size integers.

Digit Place

Units (10⁰)

Pass

1 / 3

Current Order

digit buckets (0-9)

Press "Start Sorting" to begin

How LSD Radix Sort Works

Least Significant Digit (LSD) Radix sort processes numbers starting from the units place and moves towards the most significant digit.

Bucket Distribution

Elements are placed into 10 buckets (for base-10) based on their current digit's value.

Stable Collection

Crucially, elements are collected from the buckets in FIFO order. This preserves the relative sorting done in previous digit passes.

Complexity Analysis

Time Complexity$O(d \cdot (n + k))$

Space Complexity$O(n + k)$

Comparison Based?No

Stable?Yes

Where $n$ is the number of elements, $k$ is the range of digits (10 for decimal), and $d$ is the number of digits in the largest number.

Algorithm Logic

Pseudocode

JavaScript

1for digit d from 0 to maxDigits:
2  buckets = [ [] for 10 ]
3  for x in arr:
4    digit = getDigit(x, d)
5    buckets[digit].append(x)
6  
7  arr = flatten(buckets)

Implementations

Python (LSD)

Pseudocode

Python

1def radix_sort(arr):
2    max_val = max(arr)
3    exp = 1
4    while max_val // exp > 0:
5        counting_sort_by_digit(arr, exp)
6        exp *= 10
7 
8def counting_sort_by_digit(arr, exp):
9    n = len(arr)
10    output = [0] * n
11    count = [0] * 10
12    
13    for x in arr:
14        idx = (x // exp) % 10
15        count[idx] += 1
16        
17    for i in range(1, 10):
18        count[i] += count[i-1]
19        
20    for i in range(n-1, -1, -1):
21        idx = (arr[i] // exp) % 10
22        output[count[idx] - 1] = arr[i]
23        count[idx] -= 1
24        
25    for i in range(n):
26        arr[i] = output[i]

JavaScript Implementation

Pseudocode

JavaScript

1function radixSort(arr) {
2  const max = Math.max(...arr);
3  
4  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
5    let buckets = Array.from({ length: 10 }, () => []);
6    
7    for (let num of arr) {
8      const digit = Math.floor(num / exp) % 10;
9      buckets[digit].push(num);
10    }
11    
12    arr = [].concat(...buckets);
13  }
14  
15  return arr;
16}

How LSD Radix Sort Works

Least Significant Digit (LSD) Radix sort processes numbers starting from the units place and moves towards the most significant digit.

Bucket Distribution

Elements are placed into 10 buckets (for base-10) based on their current digit's value.

Stable Collection

Crucially, elements are collected from the buckets in FIFO order. This preserves the relative sorting done in previous digit passes.

Implementations

Python (LSD)

Pseudocode

Python

1def radix_sort(arr):
2    max_val = max(arr)
3    exp = 1
4    while max_val // exp > 0:
5        counting_sort_by_digit(arr, exp)
6        exp *= 10
7 
8def counting_sort_by_digit(arr, exp):
9    n = len(arr)
10    output = [0] * n
11    count = [0] * 10
12    
13    for x in arr:
14        idx = (x // exp) % 10
15        count[idx] += 1
16        
17    for i in range(1, 10):
18        count[i] += count[i-1]
19        
20    for i in range(n-1, -1, -1):
21        idx = (arr[i] // exp) % 10
22        output[count[idx] - 1] = arr[i]
23        count[idx] -= 1
24        
25    for i in range(n):
26        arr[i] = output[i]

JavaScript Implementation

Pseudocode

JavaScript

1function radixSort(arr) {
2  const max = Math.max(...arr);
3  
4  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
5    let buckets = Array.from({ length: 10 }, () => []);
6    
7    for (let num of arr) {
8      const digit = Math.floor(num / exp) % 10;
9      buckets[digit].push(num);
10    }
11    
12    arr = [].concat(...buckets);
13  }
14  
15  return arr;
16}