Editing Counting sort (section)

==Pseudocode==
In pseudocode, the algorithm may be expressed as:

 '''function''' CountingSort(input, ''k'')
     
     count ← array of ''k'' + 1 zeros
     output ← array of same length as input
     
     '''for''' ''i'' = 0 '''to''' length(input) - 1 '''do'''
         ''j'' = key(input[''i''])
         count[''j''] = count[''j''] + 1
 
     '''for''' ''i'' = 1 '''to''' ''k'' '''do'''
         count[''i''] = count[''i''] + count[''i'' - 1]
 
     '''for''' ''i'' = length(input) - 1 '''down to''' 0 '''do'''
         ''j'' = key(input[''i''])
         count[''j''] = count[''j''] - 1
         output[count[''j'']] = input[''i'']
 
     '''return''' output

Here <code>input</code> is the input array to be sorted, <code>key</code> returns the numeric key of each item in the input array, <code>count</code> is an auxiliary array used first to store the numbers of items with each key, and then (after the second loop) to store the positions where items with each key should be placed,
<code>k</code> is the maximum value of the non-negative key values and <code>output</code> is the sorted output array.

In summary, the algorithm loops over the items in the first loop, computing a [[histogram]] of the number of times each key occurs within the <code>input</code> collection. After that in the second loop, it performs a [[prefix sum]] computation on <code>count</code> in order to determine, for each key, the position range where the items having that key should be placed; i.e. items of key <math>i</math> should be placed starting in position <code>count[<math>i</math>]</code>. Finally, in the third loop, it loops over the items of <code>input</code> again, but in reverse order, moving each item into its sorted position in the <code>output</code> array.<ref name="clrs"/><ref name="edmonds"/><ref name="sedgewick"/>

The relative order of items with equal keys is preserved here; i.e., this is a [[:Category:Stable sorts|stable sort]].