How to implement counting sort for integers in Clojure?

Question

Say I have an array of integers xs taking values from 0 to max, and I need to sort it in O(n) time, so I can't just do (sort xs).

Is there a way to do it with the frequencies function?

In another language I would then do a for to iterate over integers from 0 to max, and for each value x in that range, look up (frequencies x) and then do repeat (frequencies x) x or something.

Crucially I need to do this IN ORDER from smallest to highest, which is what makes the whole thing a sort. So I DON'T want to just map each number in xs.

Any ideas for a clojure-ish idiomatic solution?

Thanks.

Answer 1

Updating a vector isn't quite O(1) but you can use that to create the counts for each element:

(defn counting-sort [s]
  (if (empty? s)
    s
    (let [counts (reduce (fn [v e]
                           (update v e inc))
                         (vec (repeat (inc (apply max s)) 0))
                         s)]
      (apply concat (map-indexed #(repeat %2 %1) counts)))))