Radix Sort

Introduction

Radix sort is a non-comparative sorting algorithm that sorts numbers by processing individual digits. Radix means the “base” of a number system. For example, the decimal number system has a radix of 10, while the binary number system has a radix of 2. It works by sorting the input numbers based on each digit, starting from the least significant digit (LSD) to the most significant digit (MSD) or vice versa. Radix sort typically uses counting sort as a subroutine to sort the digits.

In this blog post, I would like to quickly discuss the radix sort algorithm and present a few implementations in Python and C++.

Counting Sort for Integer Numbers

The idea of counting sort is straightforward. We count the occurrences of each unique element in the input array and use this information to place each element directly into its correct position in the output array. Counting sort is efficient when the range of input values is not significantly larger than the number of elements to be sorted.

For example, consider the following array of integers:

input_array = [4, 2, 2, 8, 3, 3, 1]

We can create a count array to store the frequency of each integer:

count = [0, 1, 2, 2, 1, 0, 0, 0, 1]  # Index represents the integer value

Next, we modify the count array to store the cumulative counts instead:

count = [0, 1, 3, 5, 6, 6, 6, 6, 7]

Finally, we build the output array by placing each element in its correct position based on the count array. This can be done iteratively.

output_array = [-1, -1, -1, -1, -1, -1, -1] # Initialize output array
# Reverse iterate to maintain the stability of the sort, i.e., keep the relative order of equal elements.
for num in reversed(input_array):
    output_array[count[num] - 1] = num
    count[num] -= 1
# output_array = [1, 2, 2, 3, 3, 4, 8]

Python Implementation

The counting sort algorithm can be implemented using Python as follows.

counting_sort.py

def counting_sort(arr):

    if not arr:
        return arr

    max_val = max(arr)
    min_val = min(arr)
    range_of_elements = max_val - min_val + 1

    # Initialize count array
    count = [0] * range_of_elements
    output = [0] * len(arr)

    # Store the count of each element
    for num in arr:
        count[num - min_val] += 1

    # Change count[i] so that it contains the actual position of this element in output array
    for i in range(1, len(count)):
        count[i] += count[i - 1]

    # Build the output array
    for num in reversed(arr):
        output[count[num - min_val] - 1] = num
        count[num - min_val] -= 1

    return output

if __name__ == "__main__":

    input_array = [4, 2, 2, 8, 3, 3, 1]
    sorted_array = counting_sort(input_array)

    print("Array to be sorted:", input_array)
    print("Sorted array:", sorted_array)

$ python counting_sort.py
Array to be sorted: [4, 2, 2, 8, 3, 3, 1]
Sorted array: [1, 2, 2, 3, 3, 4, 8]

C++ Implementation

counting_sort.cpp

#include <algorithm>
#include <iostream>
#include <vector>

std::vector<int> counting_sort(std::vector<int> const& arr)
{
    if (arr.empty())
    {
        return arr;
    }

    int max_val{*std::max_element(arr.begin(), arr.end())};
    int min_val{*std::min_element(arr.begin(), arr.end())};
    int range_of_elements{max_val - min_val + 1};

    // Initialize count array
    std::vector<int> count(range_of_elements, 0);
    std::vector<int> output(arr.size());

    // Store the count of each element
    for (int const& num : arr)
    {
        count[num - min_val]++;
    }

    // Change count[i] so that it contains the actual position of this element
    // in output array
    for (size_t i{1}; i < count.size(); i++)
    {
        count[i] += count[i - 1];
    }

    // Build the output array
    for (size_t i{arr.size()}; i > 0; i--)
    {
        int num{arr[i - 1]};
        output[count[num - min_val] - 1] = num;
        count[num - min_val]--;
    }

    return output;
}

int main()
{
    std::vector<int> const input_array{4, 2, 2, 8, 3, 3, 1};
    std::vector<int> const sorted_array{counting_sort(input_array)};

    std::cout << "Array to be sorted: ";
    for (int const& num : input_array)
    {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    std::cout << "Sorted array: ";
    for (int const& num : sorted_array)
    {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

$ g++ counting_sort.cpp -o counting_sort
$ ./counting_sort
Array to be sorted: 4 2 2 8 3 3 1
Sorted array: 1 2 2 3 3 4 8

Radix Sort for Integer Numbers

Radix Sort for Non-Negative Integer Numbers

Radix sort is a non-comparative integer sorting algorithm that sorts numbers by processing individual digits. It works by sorting the input numbers based on each digit, starting from the least significant digit (LSD) to the most significant digit (MSD) or vice versa. Radix sort typically uses counting sort as a subroutine to sort the digits.

For example, consider the following array of integers:

input_array = [170, 45, 75, 90, 802, 24, 2, 66]

We can sort the array by processing each digit from the least significant to the most significant.

First, we sort the array based on the least significant digit (LSD) using counting sort:

# After sorting by LSD
output_array = [170, 90, 802, 2, 24, 45, 75, 66]

Note that because counting sort is stable, the relative order of elements with the same digit is preserved. For example, 170 comes before 90 because it appeared first in the original array.

Next, we sort the array based on the next significant digit (the tens place) using counting sort. Those with no tens digit are considered to have a tens digit of 0.

# After sorting by tens place
output_array = [802, 2, 24, 45, 66, 170, 75, 90]

Finally, we sort the array based on the most significant digit (the hundreds place) using counting sort. Similarly, those with no hundreds digit are considered to have a hundreds digit of 0.

# After sorting by hundreds place
output_array = [2, 24, 45, 66, 75, 90, 170, 802]

Python Implementation

The radix sort algorithm can be implemented using Python as follows. This implementation assumes that all input numbers are non-negative integers.

radix_sort.py

def counting_sort_for_radix(arr, exp):

    n = len(arr)
    output = [0] * n
    count = [0] * 10  # Since we are dealing with base 10

    # Store count of occurrences in count[]
    for i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1

    # Change count[i] so that it contains the actual position of this digit in output[]
    for i in range(1, 10):
        count[i] += count[i - 1]

    # Build the output array
    i = n - 1
    while i >= 0:
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1
        i -= 1

    return output

def radix_sort(arr):

    # Find the maximum number to know the number of digits
    max_val = max(arr)
    exp = 1
    output = arr
    while max_val // exp > 0:
        output = counting_sort_for_radix(output, exp)
        exp *= 10
    return output

if __name__ == "__main__":

    input_array = [170, 45, 75, 90, 802, 24, 2, 66]
    sorted_array = radix_sort(input_array)

    print("Array to be sorted:", input_array)
    print("Sorted array:", sorted_array)

$ python radix_sort.py
Array to be sorted: [170, 45, 75, 90, 802, 24, 2, 66]
Sorted array: [2, 24, 45, 66, 75, 90, 170, 802]

C++ Implementation

radix_sort.cpp

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>

std::vector<uint32_t> counting_sort_for_radix(std::vector<uint32_t> const& arr,
                                              uint32_t exp)
{
    size_t n{arr.size()};
    std::vector<uint32_t> output(n);
    std::vector<size_t> count(10, 0); // Since we are dealing with base 10

    // Store count of occurrences in count[]
    for (size_t i{0}; i < n; i++)
    {
        size_t index{(arr[i] / exp) % 10};
        count[index]++;
    }

    // Change count[i] so that it contains the actual position of this digit
    // in output[]
    for (size_t i{1}; i < 10; i++)
    {
        count[i] += count[i - 1];
    }

    // Build the output array
    for (size_t i{n}; i > 0; i--)
    {
        size_t index{(arr[i - 1] / exp) % 10};
        output[count[index] - 1] = arr[i - 1];
        count[index]--;
    }

    return output;
}

std::vector<uint32_t> radix_sort(std::vector<uint32_t> const& arr)
{
    // Find the maximum number to know the number of digits
    uint32_t max_val{*std::max_element(arr.begin(), arr.end())};
    uint32_t exp{1};
    std::vector<uint32_t> output{arr};
    while (max_val / exp > 0)
    {
        output = counting_sort_for_radix(output, exp);
        exp *= 10;
    }
    return output;
}

int main()
{
    std::vector<uint32_t> const input_array{170, 45, 75, 90, 802, 24, 2, 66};
    std::vector<uint32_t> const sorted_array{radix_sort(input_array)};

    std::cout << "Array to be sorted: ";
    for (uint32_t const& num : input_array)
    {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    std::cout << "Sorted array: ";
    for (uint32_t const& num : sorted_array)
    {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

$ g++ radix_sort.cpp -o radix_sort
$ ./radix_sort
Array to be sorted: 170 45 75 90 802 24 2 66
Sorted array: 2 24 45 66 75 90 170 802

Radix Sort for Integer Numbers

The aforementioned radix sort implementation works for non-negative integers. To make it work for all integers, we could scan the input array, find the minimum value, and shift all numbers by subtracting the minimum value before sorting. After sorting, we can shift the numbers back by adding the minimum value. This seems straightforward and will not affect the asymptotic time complexity of the algorithm.

The Correctness of Radix Sort

Radix sort is correct because it relies on the stability of the counting sort used as a subroutine. A stable sorting algorithm maintains the relative order of records with equal keys (or digits, in this case). By sorting the input array digit by digit from the least significant to the most significant, radix sort ensures that when we sort by a more significant digit, the order established by the less significant digits is preserved.

This means after sorting for those numbers which have the same number of digits they must be sorted correctly and for those which have different number of digits the sorting must be done correctly according to the number of digits. Thus, after processing all digits, the entire array is sorted correctly.

Radix Sort for Floating-Point Numbers

Radix Sort for Non-Negative Floating-Point Numbers

To extend radix sort to handle non-negative floating-point numbers, we can represent the non-negative floating-point numbers as unsigned integers using their binary representation. This will always work because the unsigned integer representation of non-negative floating-point numbers are monotonically increasing with respect to their floating-point values. Consequently, the order of non-negative floating-point numbers will be preserved when they are converted to their unsigned integer representations.

Radix Sort for Floating-Point Numbers

To extend radix sort to handle floating-point numbers, we will again represent the floating-point numbers as unsigned integers using their binary representation. However, we need to handle negative floating-point numbers carefully to ensure the correct order is preserved.

The trick is to flip the sign bit for all floating-point numbers, and for the originally negative floating-point numbers, we flip all the other bits as well. This is equivalent to flip the sign bit for positive floating-point numbers and flip all bits, i.e., one’s complement, for negative floating-point numbers. This transformation ensures that the unsigned integer representation of floating-point numbers is monotonically increasing with respect to their floating-point values, thus preserving the order.

This can be efficiently implemented using XOR operation in C++.

radix_sort_float_to_uint32.cpp

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>

uint32_t float_to_uint32(float f)
{
    uint32_t& u{reinterpret_cast<uint32_t&>(f)};
    uint32_t const mask{u & 0x80000000 ? 0xFFFFFFFF : 0x80000000};
    uint32_t const uint32_bits{u ^ mask};
    return uint32_bits;
}

float uint32_to_float(uint32_t u)
{
    uint32_t const mask{u & 0x80000000 ? 0x80000000 : 0xFFFFFFFF};
    uint32_t float_bits{u ^ mask};
    float const& f{reinterpret_cast<float&>(float_bits)};
    return f;
}

int main()
{
    std::vector<float> const floats{-3.14f, 2.71f, -1.0f, 0.0f, 1.41f, -2.0f};
    std::vector<uint32_t> uint32s(floats.size());
    // Convert floating-point numbers to their unsigned integer representations.
    std::transform(floats.begin(), floats.end(), uint32s.begin(),
                   float_to_uint32);
    // Convert back to floating-point.
    std::vector<float> reverted_floats(uint32s.size());
    std::transform(uint32s.begin(), uint32s.end(), reverted_floats.begin(),
                   uint32_to_float);

    // Output the results.
    std::cout << "Original floats:" << std::endl;
    for (float const& f : floats)
    {
        std::cout << f << " ";
    }
    std::cout << std::endl;
    std::cout << "Converted to uint32_t:" << std::endl;
    for (uint32_t const& u : uint32s)
    {
        std::cout << u << " ";
    }
    std::cout << std::endl;
    std::cout << "Reverted floats:" << std::endl;
    for (float const& f : reverted_floats)
    {
        std::cout << f << " ";
    }
    std::cout << std::endl;
}

$ g++ radix_sort_float_to_uint32.cpp -o radix_sort_float_to_uint32
$ ./radix_sort_float_to_uint32
Original floats:
-3.14 2.71 -1 0 1.41 -2
Converted to uint32_t:
1068960316 3224203428 1082130431 2147483648 3216276193 1073741823
Reverted floats:
-3.14 2.71 -1 0 1.41 -2

C++ Implementation

radix_sort_float.cpp

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>

uint32_t float_to_uint32(float f)
{
    uint32_t& u{reinterpret_cast<uint32_t&>(f)};
    uint32_t const mask{u & 0x80000000 ? 0xFFFFFFFF : 0x80000000};
    uint32_t const uint32_bits{u ^ mask};
    return uint32_bits;
}

float uint32_to_float(uint32_t u)
{
    uint32_t const mask{u & 0x80000000 ? 0x80000000 : 0xFFFFFFFF};
    uint32_t float_bits{u ^ mask};
    float const& f{reinterpret_cast<float&>(float_bits)};
    return f;
}

std::vector<uint32_t> counting_sort_for_radix(std::vector<uint32_t> const& arr,
                                              uint32_t exp)
{
    size_t n{arr.size()};
    std::vector<uint32_t> output(n);
    std::vector<size_t> count(10, 0); // Since we are dealing with base 10

    // Store count of occurrences in count[]
    for (size_t i{0}; i < n; i++)
    {
        size_t index{(arr[i] / exp) % 10};
        count[index]++;
    }

    // Change count[i] so that it contains the actual position of this digit
    // in output[]
    for (size_t i{1}; i < 10; i++)
    {
        count[i] += count[i - 1];
    }

    // Build the output array
    for (size_t i{n}; i > 0; i--)
    {
        size_t index{(arr[i - 1] / exp) % 10};
        output[count[index] - 1] = arr[i - 1];
        count[index]--;
    }

    return output;
}

std::vector<uint32_t> radix_sort(std::vector<uint32_t> const& arr)
{
    // Find the maximum number to know the number of digits
    uint32_t max_val{*std::max_element(arr.begin(), arr.end())};
    uint32_t exp{1};
    std::vector<uint32_t> output{arr};
    while (max_val / exp > 0)
    {
        output = counting_sort_for_radix(output, exp);
        exp *= 10;
    }
    return output;
}

std::vector<float> radix_sort_float(std::vector<float> const& arr)
{
    // Convert floating-point numbers to their unsigned integer representations
    std::vector<uint32_t> uint32s(arr.size());
    std::transform(arr.begin(), arr.end(), uint32s.begin(), float_to_uint32);

    // Sort the unsigned integer representations
    std::vector<uint32_t> const sorted_uint32s{radix_sort(uint32s)};

    // Convert back to floating-point
    std::vector<float> sorted_floats(sorted_uint32s.size());
    std::transform(sorted_uint32s.begin(), sorted_uint32s.end(),
                   sorted_floats.begin(), uint32_to_float);

    return sorted_floats;
}

int main()
{
    std::vector<float> const input_array{-3.14f, 2.71f,  -1.0f, 0.0f,
                                         1.41f,  -2.0f,  5.5f,  -0.5f,
                                         3.0f,   -10.2f, 7.8f,  0.1f};
    std::vector<float> const sorted_array{radix_sort_float(input_array)};

    std::cout << "Array to be sorted: ";
    for (float const& num : input_array)
    {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    std::cout << "Sorted array: ";
    for (float const& num : sorted_array)
    {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

$ g++ radix_sort_float.cpp -o radix_sort_float
$ ./radix_sort_float
Array to be sorted: -3.14 2.71 -1 0 1.41 -2 5.5 -0.5 3 -10.2 7.8 0.1
Sorted array: -10.2 -3.14 -2 -1 -0.5 0 0.1 1.41 2.71 3 5.5 7.8

Miscellaneous

Radix Sort Index Tracking

Sorting algorithms often need to return not only the sorted array but also the indices that would sort the array. This is particularly useful when we want to maintain the relationship between the sorted elements and their original positions. Because radix sort essentially performs multiple counting sorts, even though each counting sort can return a sorted index array straightforwardly, we need to carefully track the indices throughout the entire radix sort process.

In radix sort, we will maintain an auxiliary array that keeps track of the original indices of the elements. In each counting sort step, counting sort will return the a sorted index array for the array it processed. This returned indices can then be used to update our auxiliary array accordingly.

For example, suppose we have an array of four elements to be sorted by radix sort. The auxiliary index array will be initialized as [0, 1, 2, 3]. After the first counting sort, we get a sorted index array from counting sort, say [2, 0, 3, 1]. The auxiliary index array will then be updated to [2, 0, 3, 1]. In the next counting sort, we get a sorted index array, say [1, 0, 3, 2]. The auxiliary index array will then be updated to [0, 2, 1, 3].

Concretely, the update formula is as follows:

for i in range(len(auxiliary_indices)):
    updated_auxiliary_indices[i] = auxiliary_indices[sorted_indices_from_counting_sort[i]]

Radix Sort Asymptotic Complexity

It is obvious that the time complexity of counting sort is $\mathcal{O}(n + k)$, where $n$ is the number of elements in the input array and $k$ is the range of the input values. In radix sort, we perform counting sort for each digit of the maximum number in the input array. If $d$ is the number of digits in the maximum number, and we will have to perform counting sort $d$ times. Thus, the time complexity of radix sort is $\mathcal{O}(d \times (n + k))$. Because $k$ is usually pre-selected to be a constant, the time complexity of radix sort can be simplified to $\mathcal{O}(d \times n)$.

In practice, for fixed bit-width values, such as 32-bit or 64-bit integers or floating-point numbers, the number of digits $d$ is constant (e.g., for base 10, a 32-bit integer has at most 10 digits). Therefore, the time complexity of radix sort can be considered as linear, i.e., $\mathcal{O}(n)$. However, from the theoretical perspective, the numbers being sorted can be arbitrarily large, and thus $d$ cannot be treated as a constant. In such cases, the time complexity of radix sort remains $\mathcal{O}(d \times n)$.

This also means, when $n$ is very large, and $d$ remains constant or small, non-comparative sorting algorithms like radix sort can outperform comparative sorting algorithms like quicksort or mergesort, which have a time complexity of $\mathcal{O}(n \log n)$.

References

• Counting Sort
• Radix Sort
• Floating Point Value Binary Representation