# 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

### 2 Thoughts on “Counting Sort”

1. satish on August 1, 2014 at 2:19 pm said:

Algorithm is fine. But where can I get its program in c.
See this : best c compiler for windows

2. i dont understand what 4th line meaning can admin explain