AlgoViz: Interactive Algorithm Visualization Tool

Radix Sort

Category: Sorting | Time: O(d * (n+k)) | Space: O(n + k)

Input Data

Visualization

Visual representation of the data structure

Enter an algorithm and input to start visualization.

About Radix Sort

A non-comparative sorting algorithm. It avoids comparison by creating and distributing elements into buckets according to their radix. For elements with more than one significant digit, this bucketing process is repeated for each digit, while preserving the ordering of the prior step, until all digits have been considered.

Code Editor

The code is for reference. Editing it won't affect the visualization.

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

function countingSort(arr, exp) {
    let n = arr.length;
    let output = new Array(n);
    let count = new Array(10).fill(0);
    for (let i = 0; i < n; i++) {
        count[Math.floor(arr[i] / exp) % 10]++;
    }
    for (let i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }
    for (let i = n - 1; i >= 0; i--) {
        output[count[Math.floor(arr[i] / exp) % 10] - 1] = arr[i];
        count[Math.floor(arr[i] / exp) % 10]--;
    }
    for (let i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

What is Radix Sort?

How does Radix Sort work?

What is the time complexity of Radix Sort?

What is the space complexity of Radix Sort?

What does 'LSD' vs 'MSD' Radix Sort mean?

Can Radix Sort be used for strings?

Is Radix Sort a comparison-based sort?

How does Radix Sort handle numbers with different lengths?

Why must the subroutine for Radix Sort be stable?

Is Radix Sort an in-place algorithm?

Where can I learn more?