text: k is the maximum value of the non-negative key values and output 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 input collection. After that in the second loop, it performs a prefix sum computation on count in order to determine, for each key, the position range where the items having that key should be placed; i.e. items of key  should be placed starting in position count[]. Finally, in the third loop, it loops over the items of input again, but in reverse order, moving each item into its sorted position in the output array.
  The relative order of items with equal keys is preserved here; i.e., this is a stable sort.
  Complexity analysis
  Because the algorithm uses only simple for 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  times and therefore take  time. The other two for loops, and the initialization of the output array, each take  time. Therefore, the time for the whole algorithm is the sum of the times for these steps, .