Count Sort

This sorting algorithm takes advantage of the range of the numbers in the array to be sorted.
Say the range is 0..k then it can sort the array in O(k). If k is less than or equal to n, we are in great advantage because we can sort this array in linear time i.e. O(n).

The algorithm first determine for each element x the number of elements less than x. One of the advantage of this algorithm is its stability.

Following is my implementation:

void countSort(int *a, int size)
{
    int max = Max(a);
    int *c = new int[max+1];
    int *sorted = new int[size];
    for( int i=0; i<size; ++c[a[i++]] );   // Step 1
    for( i=1; i<max; c[i++] += c[i-1] );     // Step 2:Get the number of elements less than each number
    for(i=size-1; i >= 0; --i)    // Step 3
    {
        sorted[c[a[i]]-1] = a[i];
        --c[a[i]];
    }
    for(i=0; i<size; ++i)
        a[i] = sorted[i];
}

Example --

Input Array   

2

5

3

0

2

3

0

3

Step 1: Array C

2

0

2

3

0

1

Step 2: Array C

2

2

4

7

7

8

Step 3:

 a[7] = 3  c[3] = 7 sorted [6] = 3 => c[3] = 6

3

a[6] = 0  c[0] = 2  sorted[1] = 0  => c[0] = 1

0

3

a[5] = 3  c[3] = 6  sorted[5] = 3  => c[3] = 5

0

3

3

.

.

.

.

In the End Sorted array

0

0

2

2

3

3

3

5