ここでは、 Haskellで分布数えソート(計数ソート、counting sort)を実装してみましょう。 分布数えソートを知らない人は このページ を参照してください。 Haskell による分布数えソートの実装は以下のようになります。
accumArray 等、Haskell の配列について知らない人は このページ を参照してください。
はい、皆さんの言いたいことは分かります。そうですね、 この分布数えソートの実装、 こんな回りくどいことをするくらいなら素直に バケットソート をした方がよいですね。ただ、それでも計算量は一応 \(O(n)\) です。 結構速いんですよ。まあ、 うまくソート出来るのは、 ソートのキーの定義域が十分小さい整数の区間の場合に限られますけどね。
分布数えソートは、 配列の副作用を前提とした非常に高速なアルゴリズムなのですが、 副作用が原則禁止されている Haskell ではあまり効率的に書けません。 このあたりに純粋な関数型プログラミングの限界があるように個人的には思います。副作用を使ったらどうなるか、 興味のある人は こちらのページ へどうぞ。