Bucket sort (Clojure)
(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)