Clojureでバケツソート

正の整数のシーケンスxsをO(n+m)時間でソートする方法としてBucket Sortがある。

0からxsの最大値mまで番号が付けられているvector of vectorを作成して、xsの全要素を一つずつ対応するvectorに入れていく。あとはconcatするだけ。

(defn bucket-sort [xs]
  (let [bucket-count (inc (apply max xs))
        buckets      (into [] (repeat bucket-count []))
        add-item     (fn [buckets item] 
                       (update-in buckets 
                                  [item] 
                                  #(conj % item)))]
    (apply concat 
           (reduce add-item buckets xs))))

xsの最大値を見つけるのにO(n)、vector of vectorを作成するのにO(m)、xsの要素一つをvectorに入れるのはindex lookupがO(1)でvector insertionもO(1)、それをn分やるのでO(n)。concatにO(n)。

O(n)のプロセスが三つとO(m)が一つ。O(n+m)で、nとmのどちらがdominateするかは状況次第。

もしmが相対的にはnに比べて小さく、そして絶対的にはメモリが許すくらいに小さいなら、非常にありがたいソート手法である。実際走らせてみると早い。