1.Previous
3.Next

of the elements ordered by their keys. Because of its application to radix sorting, counting sort must be a stable sort; that is, if two elements share the same key, their relative order in the output array and their relative order in the input array should match.

Pseudocode

In pseudocode, the algorithm may be expressed as:

function CountingSort(input, k) is 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

1.Previous
3.Next