SimuVedaAlgorithms Lab Open in the lab

Sorting / Intermediate

Radix Sort (LSD) Visualizer

Sort by the ones digit, then by the tens digit, keeping ties in their previous order. After the last digit the whole array is sorted, without comparing two values.

Start the Radix Sort (LSD) simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(d·(n + 10))
Average timeO(d·(n + 10))
Worst timeO(d·(n + 10))
Extra spaceO(n + 10)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. The largest value is 8, so 1 digit pass are needed. [5, 1, 4, 2, 8]
  2. Pass for the ones digit. Start with 10 empty buckets.
  3. 5 has ones digit 5. Drop it in bucket 5.
  4. 1 has ones digit 1. Drop it in bucket 1.
  5. 4 has ones digit 4. Drop it in bucket 4.
  6. 2 has ones digit 2. Drop it in bucket 2.
  7. 8 has ones digit 8. Drop it in bucket 8.
  8. Read the buckets back in order 0 to 9. The array is now sorted by the ones digit. [1, 2, 4, 5, 8]
  9. Sorted with 5 reads and zero comparisons.

Try it with your own input →

Radix sort (LSD) in Java, Python, C++, C and JavaScript

void radixSort(int[] a) {
  int max = Arrays.stream(a).max().getAsInt();
  for (int exp = 1; max / exp > 0; exp *= 10) {
    List<List<Integer>> buckets = new ArrayList<>();
    for (int d = 0; d < 10; d++) buckets.add(new ArrayList<>());
    for (int x : a) buckets.get((x / exp) % 10).add(x);
    int k = 0;
    for (List<Integer> b : buckets)
      for (int x : b) a[k++] = x;
  }
}
def radix_sort(a):
    max_v = max(a)
    exp = 1
    while max_v // exp > 0:
        buckets = [[] for _ in range(10)]
        for x in a:
            buckets[(x // exp) % 10].append(x)
        k = 0
        for b in buckets:
            for x in b:
                a[k] = x; k += 1
        exp *= 10
void radixSort(vector<int>& a) {
  int mx = *max_element(a.begin(), a.end());
  for (int exp = 1; mx / exp > 0; exp *= 10) {
    vector<vector<int>> buckets(10);
    for (int x : a) buckets[(x / exp) % 10].push_back(x);
    int k = 0;
    for (auto& b : buckets)
      for (int x : b) a[k++] = x;
  }
}
#include <stdlib.h>

void radixSort(int a[], int n) {
  int max = a[0];
  for (int x = 1; x < n; x++) if (a[x] > max) max = a[x];
  int *out = malloc(n * sizeof(int));
  for (int exp = 1; max / exp > 0; exp *= 10) {
    int count[10] = {0};
    for (int x = 0; x < n; x++) count[(a[x] / exp) % 10]++;
    for (int d = 1; d < 10; d++) count[d] += count[d - 1];
    for (int x = n - 1; x >= 0; x--) out[--count[(a[x] / exp) % 10]] = a[x];
    int k = 0;
    for (int x = 0; x < n; x++)
      a[k++] = out[x];
  }
  free(out);
}
function radixSort(a) {
  const max = Math.max(...a);
  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
    const buckets = Array.from({ length: 10 }, () => []);
    for (const x of a) buckets[Math.floor(x / exp) % 10].push(x);
    let k = 0;
    for (const b of buckets)
      for (const x of b) a[k++] = x;
  }
}

In an interview

Each pass must be stable, or the work of earlier digits is lost. That is why each digit pass is a counting sort that keeps ties in order.

More sorting