Counting Sort

Counting sort is a linear time sorting algorithm used to sort items when they belong to a fixed and finite set. Integers which lie in a fixed interval, say k1 to k2, are examples of such items.

Algorithm:

1. Count for every key j, 1 ≤ j ≤ m how often it occurs in the input array. Store results in an array C.

2. The counting information stored in C can be used to determine the position of each element in the sorted array. Suppose we modify the values of the C [ j ] so that now C [ j ] = the number of keys less than or equal to j . Then we know that the elements with key “ j ” must be stored at the indices C [ j − 1 ]+ 1 ,…, C [ j ] of the final sorted array.

3. We use a “trick” to move the elements to the right position of an auxiliary array. Then we copy the sorted auxiliary array back to the original one.

The algorithm makes two passes over A and one pass over B. If size of the range k is smaller than size of input n, then time complexity=O(n). Also, note that it is a stable algorithm, meaning that ties are resolved by reporting those elements first which occur first.

void countSort(int * arr)
{
    // The output array that will have sorted  arr
    int output[ count( arr)];
 
    // Create a count array to store count of individual element and
    // initialize count array as 0
    int count[RANGE + 1], i;
    memset(count, 0, sizeof(count));
 
    // Store count of each element
    for(i = 0;  arr[i]; ++i)
        ++count[ arr[i]];
 
    /* modified count array indicates the position of each object in 
	the output sequence. */
    for (i = 1; i <= RANGE; ++i)
        count[i] += count[i-1];
 
    // Build the output array
    for (i = 0;  arr[i]; ++i)
    {
        output[count[ arr[i]]-1] =  arr[i];
        --count[ arr[i]];
    }
 
    // Copy the output array to  arr
    for (i = 0;  arr[i]; ++i)
         arr[i] = output[i];
}

Time Complexity: O(n+k) where n is the number of elements in input array and k is the range of input.
Auxiliary Space: O(n+k)

Source: Counting Sort