8. Count Sort

Count sort is a non-comparison based sorting algorithm that simply counts how many occurances an integers and places integers in their correct sorted positions.

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

    int[] count = new int[max + 1];

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

    int j = 0;
    for (int i = 0; i < array.length; i++) {
        if (count[j] == 0) {
            j++;
            i--;
        } else {
            array[i] = j;
            count[j]--;
        }
    }
}

This algorithm has a time complexity of $O(n)$ which is really good and a space complexity of $O(n)$ which is okay.

Next Page →