Exploring Time and Space Complexities of Radix Sort

Radix sort processes the digits of numbers individually, starting from the least significant digit to the most significant digit or vice versa.

It uses a stable sorting algorithm (such as counting sort) as a subroutine.

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    for i in arr:
        index = (i // exp) % 10
        count[index] += 1

    for i in range(1, 10):
        count[i] += count[i - 1]

    for i in range(n - 1, -1, -1):
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1

    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        counting_sort(arr, exp)
        exp *= 10

#include <vector>
#include <algorithm>
using namespace std;

template <typename T>
void counting_sort(vector<T>& arr, int exp, bool (*get_digit)(T, int)) {
    int n = arr.size();
    vector<T> output(n);
    int count[10] = {0};

    for (int i = 0; i < n; i++) {
        int index = get_digit(arr[i], exp);
        count[index]++;
    }

    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    for (int i = n - 1; i >= 0; i--) {
        int index = get_digit(arr[i], exp);
        output[count[index] - 1] = arr[i];
        count[index]--;
    }

    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

template <typename T>
void radix_sort(vector<T>& arr, bool (*get_digit)(T, int)) {
    T max_val = *max_element(arr.begin(), arr.end());
    for (int exp = 1; max_val / exp > 0; exp *= 10) {
        counting_sort(arr, exp, get_digit);
    }
}

Time Complexity: O(n.d)

The time complexity of radix sort depends on two factors:

• n - The number of elements to be sorted.
• d - The number of digits in the largest number in the dataset.

Radix sort iterates over each element in the input list. So, for each pass over the data, the algorithm processes all n elements.

Radix sort then processes the numbers digit by digit.

Therefore, the time complexity of radix sort is O(n.d) in all cases.

Space Complexity of Radix Sort: O(n+d)

Radix sort requires additional space for the output array and the count array used in counting sort.

Thus, the space complexity depends on the size of the input array and the base used for digit extraction, resulting in O(n+d) complexity.

When to Use Radix Sort?

When to Use:

1. Large and Uniform Datasets: Heap sort is great for sorting large datasets with uniformly distributed keys.
2. Small d Value: Heap sort is also good for datasets where the input keys have a small range of digits (d is small).

For example, consider the following array:

125, 145, 215, 245, 305

Here, all the numbers have 3 digits, which is a small d value. Radix sort is suitable for such uniformly distributed values with small d values.

When to Avoid:

1. Large d Values: Datasets with a very large number of digits in their elements, as d becomes significant.

Let's take another example:

1, 10, 50, 70, 7653678

Here, the dataset is not uniform. Most of the elements have two digits but one outlier (7653678) has 7 digits.

This results in a d value of 7, which is very large. Radix sort is not suitable for such datasets, especially when the dataset is large.