Radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value. It processes the digits from least significant to most significant.

How it Works

Radix sort works by processing each digit of the numbers from the least significant to the most significant. It uses counting sort as a subroutine to sort the digits.


void radixSort(int[] arr) {
    int max = getMax(arr);
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countSort(arr, exp);
    }
}

void countSort(int[] arr, int exp) {
    int output[] = new int[arr.length];
    int count[] = new int[10];
    for (int i = 0; i < arr.length; i++) {
        count[(arr[i] / exp) % 10]++;
    }
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }
    for (int i = arr.length - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }
    for (int i = 0; i < arr.length; i++) {
        arr[i] = output[i];
    }
}

int getMax(int[] arr) {
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

Example Explanation

Consider an array [170, 45, 75, 90, 802, 24, 2, 66]. The radix sort will first sort these numbers based on the unit place, then the tenth place, and so on.

Console Output:

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

Radix Sort on Strings

Sorting Strings

Radix sort can be adapted for sorting strings by processing characters from right to left. This is particularly useful for fixed-length strings.


void radixSortStrings(String[] arr, int maxLen) {
    for (int exp = maxLen - 1; exp >= 0; exp--) {
        countSortStrings(arr, exp);
    }
}

void countSortStrings(String[] arr, int charIndex) {
    int n = arr.length;
    String output[] = new String[n];
    int count[] = new int[256]; // ASCII character set

    for (int i = 0; i < n; i++) {
        count[arr[i].charAt(charIndex)]++;
    }
    for (int i = 1; i < 256; i++) {
        count[i] += count[i - 1];
    }
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i].charAt(charIndex)] - 1] = arr[i];
        count[arr[i].charAt(charIndex)]--;
    }
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

Example Explanation

For an array of strings ["abc", "xyz", "bcd", "acd"], radix sort will sort them character by character starting from the last character.

Console Output:

["abc", "acd", "bcd", "xyz"]

Radix Sort with Negative Numbers

Handling Negatives

Radix sort can be adapted to handle negative numbers by separating them into positive and negative arrays, sorting each, and then combining them.


void radixSortWithNegatives(int[] arr) {
    List positives = new ArrayList<>();
    List negatives = new ArrayList<>();

    for (int num : arr) {
        if (num < 0) negatives.add(-num);
        else positives.add(num);
    }

    int[] posArray = positives.stream().mapToInt(i -> i).toArray();
    int[] negArray = negatives.stream().mapToInt(i -> i).toArray();

    radixSort(posArray);
    radixSort(negArray);

    for (int i = 0; i < negArray.length; i++) {
        arr[i] = -negArray[negArray.length - 1 - i];
    }
    for (int i = 0; i < posArray.length; i++) {
        arr[negArray.length + i] = posArray[i];
    }
}

Example Explanation

Given an array [-5, -10, 0, 5, 3, -1], the radix sort will separate negatives and positives, sort them individually and then combine them.

Console Output:

[-10, -5, -1, 0, 3, 5]

Radix Sort for Floating Points

Floating Point Adaptation

Radix sort is not directly applicable to floating-point numbers due to their representation. A common workaround is to multiply by a power of ten to convert them into integers.


void radixSortFloats(float[] arr) {
    int factor = 1000; // Example factor to convert float to int
    int[] intArr = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        intArr[i] = (int)(arr[i] * factor);
    }
    radixSort(intArr);
    for (int i = 0; i < arr.length; i++) {
        arr[i] = (float)intArr[i] / factor;
    }
}

Example Explanation

For an array [1.23, 0.56, 4.78, 2.34], the radix sort will convert them to integers [1230, 560, 4780, 2340], sort them, and convert back.

Console Output:

[0.56, 1.23, 2.34, 4.78]

Radix Sort on Large Numbers

Handling Large Numbers

Radix sort is effective for sorting large numbers as it processes each digit independently. This makes it efficient for datasets with large values.


void radixSortLargeNumbers(long[] arr) {
    long max = getMax(arr);
    for (long exp = 1; max / exp > 0; exp *= 10) {
        countSort(arr, exp);
    }
}

void countSort(long[] arr, long exp) {
    long output[] = new long[arr.length];
    int count[] = new int[10];
    for (int i = 0; i < arr.length; i++) {
        count[(int)((arr[i] / exp) % 10)]++;
    }
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }
    for (int i = arr.length - 1; i >= 0; i--) {
        output[count[(int)((arr[i] / exp) % 10)] - 1] = arr[i];
        count[(int)((arr[i] / exp) % 10)]--;
    }
    for (int i = 0; i < arr.length; i++) {
        arr[i] = output[i];
    }
}

long getMax(long[] arr) {
    long max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

Example Explanation

For an array of large numbers [123456789, 987654321, 567890123, 234567890], radix sort will efficiently sort them by processing each digit.

Console Output:

[123456789, 234567890, 567890123, 987654321]