9. Radix Sort

Radix sort is another-comparison based sorting algorithm which puts data into buckets then takes data out of the buckets into sorted order. We can use radix sort for integers (shown below), strings, etc. of the same length.

/**
@param array an array of positive integers.
*/
public void radixSort(int[] array) {
    int max = array[0];
    for (int i = 1; i < array.length; i++) {
        if (max < array[i]) {
            max = array[i];
        }
    }

    for(int place = 1; max / place > 0; place *= 10) {
        int output[] = new int[array.length];
        int count[] = new int[10];

        for (int i = 0; i < array.length; i++) {
            count[(array[i] / place) % 10]++;
        }

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

        for (int i = array.length - 1; i >= 0; i--) {
            output[count[(array[i] / place) % 10] - 1] = array[i];
            count[(array[i] / place) % 10]--;
        }

        for (int i = 0; i < array.length; i++) {
            array[i] = output[i];
        }
    }
}

Radix sort runs in $O(n)$ time complexity and $O(n)$ space complexity.

Next Page →