How To Do Radix Sort in JavaScript

Radix Sort is a non-comparative integer sorting algorithm that sorts numbers by processing individual digits. It is particularly efficient when dealing with numbers and can perform better than traditional comparison-based algorithms like Quick Sort or Merge Sort for large datasets of integers.

In this post, we’ll walk through how to implement Radix Sort in JavaScript, explain the algorithm step-by-step, and discuss its time and space complexities.

What is Radix Sort?

Radix Sort processes the digits of numbers starting from the least significant digit (LSD) or the most significant digit (MSD). For each digit, a stable sorting algorithm (like Counting Sort) is used to sort the numbers. This process repeats until all digits have been processed, resulting in a fully sorted array.

Radix Sort is mainly used to sort integers but can also be extended to strings or floating-point numbers with proper modifications.

Pseudocode for Radix Sort

procedure radixSort(arr)
    # Step 1: Find the maximum number in the array to determine the maximum number of digits
    maxNumber = findMax(arr)
    d = number of digits in maxNumber

    # Step 2: Perform a stable sort (like Counting Sort) on each digit from least significant to most significant
    for i = 0 to d - 1 do
        arr = countingSortByDigit(arr, i)
    return arr


procedure countingSortByDigit(arr, digitIndex)
    n = length of arr
    output = new array of size n       # Output array to store the sorted numbers
    count = new array of size 10       # Count array to store the frequency of digits (0 to 9)

    # Step 3: Initialize the count array to 0
    for i = 0 to 9 do
        count[i] = 0

    # Step 4: Store the count of occurrences of each digit
    for i = 0 to n - 1 do
        digit = getDigit(arr[i], digitIndex)  # Extract the digit at the digitIndex
        count[digit] = count[digit] + 1

    # Step 5: Change the count array so that it contains the position of each digit in the output array
    for i = 1 to 9 do
        count[i] = count[i] + count[i - 1]

    # Step 6: Build the output array by placing elements at the correct positions based on the count array
    for i = n - 1 down to 0 do
        digit = getDigit(arr[i], digitIndex)
        output[count[digit] - 1] = arr[i]
        count[digit] = count[digit] - 1

    # Step 7: Copy the sorted output back into the original array
    for i = 0 to n - 1 do
        arr[i] = output[i]

    return arr


procedure getDigit(num, digitIndex)
    # Step 8: Get the digit at the digitIndex (e.g., for ones place, digitIndex = 0; for tens place, digitIndex = 1)
    return floor(abs(num) / 10^digitIndex) % 10

Explanation of the Pseudocode

Main Radix Sort Function (radixSort)

1. Find the Maximum Number:
   • The first step is to find the maximum number in the array to determine how many digits the largest number has. This will help us know how many passes (or iterations) we must sort by each digit.
   • For example, if the largest number is 802, it has three digits. So we need three passes (one for the ones, tens, and hundreds places).
2. Loop Over Each Digit:
   • Starting from the least significant digit (LSD), sort the array based on that digit using a stable sorting algorithm.
   • In Radix Sort, this sorting is done using Counting Sort for each digit.
   • We repeat this process for each digit until we have sorted the array by the most significant digit (MSD).

Time Complexity of Radix Sort

• Best Case: O(n * k) – where n is the number of elements and k is the number of digits in the largest number. Radix Sort’s performance does not depend on element comparisons, making it efficient for numbers with a fixed number of digits.
• Average Case: O(n * k) – The time complexity remains linear for average cases, making it highly efficient for sorting large datasets of numbers.
• Worst Case: O(n * k) – Radix Sort’s worst-case complexity is still linear, which makes it better than comparison-based sorting algorithms like Quick Sort and Merge Sort for large datasets of integers.

Space Complexity of Radix Sort

• Space Complexity: O(n + k) – Radix Sort requires extra space to store the buckets for grouping numbers by their digits.

JavaScript Implementation of Radix Sort

Here’s how you can implement Radix Sort in JavaScript, focusing on the least significant digit (LSD) version:

// A utility function to get the digit at a given place value
function getDigit(num, place) {
    return Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
}

// A utility function to count the number of digits in the largest number
function digitCount(num) {
    return num === 0 ? 1 : Math.floor(Math.log10(Math.abs(num))) + 1;
}

// A function to find the maximum number of digits in the array
function mostDigits(arr) {
    let maxDigits = 0;
    for (let num of arr) {
        maxDigits = Math.max(maxDigits, digitCount(num));
    }
    return maxDigits;
}

// Radix Sort function
function radixSort(arr) {
    const maxDigitCount = mostDigits(arr);
    
    // Loop through each digit place (ones, tens, hundreds, etc.)
    for (let k = 0; k < maxDigitCount; k++) {
        // Create buckets for each digit (0 to 9)
        let digitBuckets = Array.from({ length: 10 }, () => []);

        // Place each number in the corresponding bucket based on the k-th digit
        for (let i = 0; i < arr.length; i++) {
            let digit = getDigit(arr[i], k);
            digitBuckets[digit].push(arr[i]);
        }

        // Flatten the buckets back into the array
        arr = [].concat(...digitBuckets);
    }

    return arr;
}

// Example usage
const arr = [170, 45, 75, 90, 802, 24, 2, 66];
console.log("Initial array:", arr);
console.log("Sorted array:", radixSort(arr));

Explanation:

• getDigit(num, place): Extracts the digit from a number at a specific place (ones, tens, hundreds, etc.).
• digitCount(num): Returns the number of digits in a given number.
• mostDigits(arr): Finds the maximum number of digits among all numbers in the array.
• radixSort(arr): Sorts the array by iterating over each digit (from least significant to most significant) and using buckets (0-9) to group numbers by their digits. After each pass, the array is flattened, and the process continues with the next digit.

Step-by-Step Walkthrough of Radix Sort

Let’s walk through Radix Sort using the array [170, 45, 75, 90, 802, 24, 2, 66].

Step 1: Sort by the Ones Place

• Group the numbers by the digit in the ones place:
  • 0: [170, 90]
  • 2: [802, 2]
  • 4: [24]
  • 5: [45, 75]
  • 6: [66]
• Flatten the array: [170, 90, 802, 2, 24, 45, 75, 66]

---

Step 2: Sort by the Tens Place

• Group the numbers by the digit in the tens place:
  • 0: [2]
  • 2: [24]
  • 4: [45]
  • 6: [66]
  • 7: [170, 75]
  • 8: [802]
  • 9: [90]
• Flatten the array: [2, 24, 45, 66, 170, 75, 802, 90]

---

Step 3: Sort by the Hundreds Place

• Group the numbers by the digit in the hundreds place:
  • 0: [2, 24, 45, 66, 75, 90]
  • 1: [170]
  • 8: [802]
• Flatten the array: [2, 24, 45, 66, 75, 90, 170, 802]

At this point, the array is fully sorted.

Pros and Cons of Using Radix Sort

Pros:

1. Linear Time Complexity: Radix Sort can outperform comparison-based algorithms (O(n log n)) when dealing with large datasets of integers.
2. Non-Comparative: Unlike Quick Sort or Merge Sort, Radix Sort doesn’t compare elements directly, which can lead to faster sorting times for certain types of data.
3. Stable Sorting: Radix Sort is stable when paired with a stable sub-algorithm like Counting Sort, meaning that the relative order of equal elements is preserved.

Cons:

1. Requires Extra Space: Radix Sort requires extra space for the digit buckets, which can be a limitation in memory-constrained environments.
2. Limited to Integers: Radix Sort works well for integers, but it’s more complex to implement for floating-point numbers or strings.
3. Dependent on Number of Digits: Radix Sort’s performance is dependent on the number of digits in the largest number (k), which can make it slower for numbers with many digits.

When to Use Radix Sort

Radix Sort is particularly effective when:

1. You’re sorting integers: Radix Sort excels at sorting integers with a fixed number of digits.
2. You need linear-time sorting: With a time complexity of O(n * k), Radix Sort can outperform comparison-based algorithms for large datasets of integers.
3. You have a large dataset: When dealing with large numbers or datasets, Radix Sort can be more efficient than Quick Sort or Merge Sort.

However, due to its space requirements, Radix Sort may not be ideal for non-integer data types or memory-constrained environments.

Conclusion

Radix Sort is a highly efficient, non-comparative sorting algorithm for integers. Processing each digit of the numbers individually achieves linear time complexity in many cases, making it an excellent choice for large datasets of integers. While it requires extra space for the digit buckets, its ability to sort numbers in linear time makes it a valuable algorithm for specific scenarios.

Congratulations on reading to the end of the tutorial!

Read the following articles to learn how to implement Radix Sort:

In Python – How to do Radix Sort in Python

In C++ – How to Do Radix Sort in C++

Have fun and happy researching!