(defn bucket-sort "Runs in O(n) time." [items] (let [len (count items) mx (apply max items) bucket-size (inc (int (/ mx len))) buckets (reduce (fn [v n] (conj v [])) [] (range (+ bucket-size (/ mx bucket-size))))] (letfn [(distrib-nums [v n] (let [ind (int (/ n bucket-size)) bucket (nth v ind)] (assoc! v ind (conj bucket n))))] (let [pre-buckets (persistent! (reduce distrib-nums (transient buckets) items))] (apply concat (map (fn [bucket] (when (> (count bucket) 0) (insertion-sort bucket))) pre-buckets))))))

Runs slightly faster than Clojure’s built-in sort (at least on integers in the range 0 to 1E6) :

java version "1.6.0_18" OpenJDK Runtime Environment (IcedTea6 1.8) (6b18-1.8-0ubuntu1) OpenJDK 64-Bit Server VM (build 14.0-b16, mixed mode) (let [cnt 1e6 rnums (map (fn [n] (int (rand cnt))) (range cnt))] ;; warmup (doseq [c (range 10)] (take 10 (bucket-sort rnums)) (take 10 (sort rnums))) ;; run (println (time (take 10 (bucket-sort rnums)))) (println (time (take 10 (sort rnums))))) "Elapsed time: 676.618148 msecs" (0 0 1 1 4 4 5 7 8 10) "Elapsed time: 897.640471 msecs" (0 0 1 1 4 4 5 7 8 10)