Editing Counting sort (section)

==Complexity analysis==
Because the algorithm uses only simple <code>for</code> loops, without recursion or subroutine calls, it is straightforward to analyze. The initialization of the count array, and the second for loop which performs a prefix sum on the count array, each iterate at most {{math|''k'' + 1}} times and therefore take {{math|''O''(''k'')}} time. The other two for loops, and the initialization of the output array, each take {{math|''O''(''n'')}} time. Therefore, the time for the whole algorithm is the sum of the times for these steps, {{math|''O''(''n'' + ''k'')}}.<ref name="clrs"/><ref name="edmonds"/>

Because it uses arrays of length {{math|''k'' + 1}} and {{mvar|n}}, the total space usage of the algorithm is also {{math|''O''(''n'' + ''k'')}}.<ref name="clrs"/> For problem instances in which the maximum key value is significantly smaller than the number of items, counting sort can be highly space-efficient, as the only storage it uses other than its input and output arrays is the Count array which uses space {{math|''O''(''k'')}}.<ref>{{citation
 | last1 = Burris | first1 = David S.
 | last2 = Schember | first2 = Kurt
 | contribution = Sorting sequential files with limited auxiliary storage
 | doi = 10.1145/503838.503855
 | location = New York, NY, USA
 | pages = 23–31
 | publisher = ACM
 | title = Proceedings of the 18th annual Southeast Regional Conference
 | year = 1980| isbn = 0897910141
 | s2cid = 5670614
 }}.</ref>