GargoyleLizy · February 15, 2019 11:19 · Feb 15, 2019
diff --git a/CountingSort.kt b/CountingSort.kt
@@ -0,0 +1,21 @@
+/**
+ * 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
+    }
+}