Editing Counting sort (section)

==Input and output assumptions==
In the most general case, the input to counting sort consists of a [[collection (abstract data type)|collection]] of {{mvar|n}} items, each of which has a non-negative integer key whose maximum value is at most {{mvar|k}}.<ref name="sedgewick"/>
In some descriptions of counting sort, the input to be sorted is assumed to be more simply a sequence of integers itself,<ref name="clrs"/> but this simplification does not accommodate many applications of counting sort. For instance, when used as a subroutine in [[radix sort]], the keys for each call to counting sort are individual digits of larger item keys; it would not suffice to return only a sorted list of the key digits, separated from the items.

In applications such as in radix sort, a bound on the maximum key value {{mvar|k}} will be known in advance, and can be assumed to be part of the input to the algorithm. However, if the value of {{mvar|k}} is not already known then it may be computed, as a first step, by an additional loop over the data to determine the maximum key value.

The output is an [[Array data structure|array]] 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.<ref name="clrs"/><ref name="edmonds"/>