Counting Sort - The Algorithm

The Algorithm

In summary, the algorithm loops over the items, computing a histogram of the number of times each key occurs within the input collection. It then performs a prefix sum computation (a second loop, over the range of possible keys) to determine, for each key, the starting position in the output array of the items having that key. Finally, it loops over the items again, moving each item into its sorted position in the output array.

In pseudocode, this may be expressed as follows:

''' allocate an array Count ; initialize each array cell to zero ; THEN ''' for each input item x: Count = Count + 1 total = 0 for i = 0, 1, ... k: c = Count Count = total total = total + c ''' allocate an output array Output ; THEN ''' for each input item x: store x in Output] Count = Count + 1 return Output

After the first for loop, Count stores the number of items with key equal to i. After the second for loop, it instead stores the number of items with key less than i, which is the same as the first index at which an item with key i should be stored in the output array. Throughout the third loop, Count always stores the next position in the output array into which an item with key i should be stored, so each item is moved into its correct position in the output array. The relative order of items with equal keys is preserved here, i.e. this is a stable sort.