ここでは、Haskellで基数ソート(radix sort)を実装してみましょう。 基数ソートを知らない人は このページ を参照してください。
バケットソートは計算量が \(O(n)\) と高速ですが、 ソートのキーの定義域が十分に小さい整数の区間でないとソート困難という制限があります。 基数ソートは定義域が大きな整数区間でもソート出来る計算量 \(O(n)\) の安定ソートです。キーを何桁かの桁に分け、 下位の桁から順々にバケットソートします。 バケットソートは安定なソートなので、 段階的にソートすることで一挙にソートするのと同じ効果が得られます。 一方で、ソートに必要な配列のサイズは比較的小さいままで済みます。
それでは、Haskell による基数ソートの実装を以下に示します。
accumArray 等、Haskell の配列について知らない人は このページ を参照してください。
uncurry (flip (++)) $ break ((< 0) . getkey)
というコードが意味不明かもしれませんが、
これは要素に負の数が含まれていたときの補正を行うコードです。
負の数はビットパターンで見ると最上位ビットが
1 の非常に大きい数と見なせます。
上記のアルゴリズムでは負の数を非常に大きな数として扱いますので、
そのままでは負の数が後ろの方に並んでしまいます。
そこで、それを前に移動するのがこのコードです。