Counting Sort Algorithm

Counting sort runs on relatively smaller set of input. Counting sort calculates, for every element in array - X, the number of elements which are lesser than - X. It then use this information to put X directly into its position in sorted array.

Selection sort takes two additional array.

One for result, the sorted array
other for temporary storage, where size equals to the maximum number on input array.

Its interesting to note that this algorithm is not a comparison sort. You will not see any comparison in code. This algorithm uses elements values to index into array.

Counting Sort Example

Count Sort Algorithm

First iterate on input array, and calculate each number occurence in the 2nd additional array (lets call it C).
After the iteration, The array-C’s index will denote the input number, and the value contains how many times the number comes in original array. In the image above, see part-a.
Run one more iteration on array-c. And, accumulate the sum. See above image, part-b
Now iterate equal to length of original array (from last index to 0):
- For the number in original array, use it as index in array-C, which will give you its position in sorted array
- Put this number in sorted array at position told by array-c
- Decrement this value from array-c by 1
At the end, we will get sorted array.

See the code here:

public class CountSort {
    private int[] arr;

    public CountSort(int[] arr) {
        this.arr = arr;
    }

    /**
     * Count sort, max value-k
     * @param k, the max value in array
     */
    public int[] doSort(int k) {
        int[] c = new int[k+1];

        //count number of occurence
        for (int i=0; i<this.arr.length; i++) {
            c[this.arr[i]] ++;
        }

        //accumulate
        for (int i=1; i<c.length; i++) {
            c[i] += c[i-1];
        }
        int[] result = new int[this.arr.length];

        //put the number to its designated place
        for (int i=this.arr.length-1; i>=0; i--) {
            result[c[this.arr[i]]-1] = this.arr[i];
            c[this.arr[i]] --;
        }

        return result;
    }
}

Key Points

It is not a comparison sort.
It is a stable sort.
This uses 2 additional arrays.
It is used for relatively smaller set of numbers.
The maximum number in array should be order of size of array. Example: this algorithm is good for sorting age of people.
Performance is very good. its time complexity is O(n + k) ~= O(n)