/**
 * Counting Sort assumes every element of input array was inside [0,k]
 */
object CountingSort {

    fun sort(input: Array<Int>, upperLimit: Int): Array<Int> {
        val C = IntArray(upperLimit + 1) { 0 }
        val output = Array<Int>(input.size) { 0 }
        input.forEach { element ->
            C[element]++
        }
        for (i in 1..upperLimit) {
            C[i] = C[i] + C[i - 1]
        }
        for (i in output.size - 1 downTo 0) {
            output[C[input[i]]-1] = input[i]
            C[input[i]]--
        }
        return output
    }
}