バケットソート
計算量の種明かしは「バケットソートの分割統治」の項で行ったとおりで、利点とはなっていない。
比較を行なわずにソートできる点は利点となる。
しかしながら、その裏返しとして、ソート対象の値のモデルに合わせてプログラムを書く必要が生じてしまう。
バケットソート(英: bucket sort)は、ソートのアルゴリズムの一つ。バケツソート、ビンソート(英: bin sort)などともいう。バケツ数 k 個使った場合、オーダーはO(n + k)となり、ソートする要素数nとk を無関係にできる場合線形時間ソートとなるが、要素間の全順序関係を用いるソートとは異なり、キーの取りうる値がk種類である、という入力により強い制限を要求するソートである。
バケットソートのバケツをメモリ空間の代わりに時間に置き換えたもので、もともと掲示板4chanに投稿されたアイデアである。
「全要素の最大値×スリープさせる単位時間」で実際にソートできてしまう。それが役に立つ事例は例題程度であろう。
面白いジョークであるが、実際のコンピュータシステムでは、起動したプロセスが意図した時間にピタリと正確に終了するという保証はない。すなわち、非同期に複数プロセスを起動したとき、混雑やOSの制御のために値が返ってくる順序が意図した時刻にこないことがあるのはもちろん、ソートで期待する順序とは異なった順序で返ってくる恐れさえある。したがって、デモや冗談ならともかく、実用には絶対使ってはいけない。
OSは、実は一定時間後に起動する要求を到来時間順の待ち行列につないで管理している。そのとき当然到来時間の大小比較が行われる。タイマで見張り、時間の到来した要求を行列から外して要求元の待ちを解除し結果を通知しているのが実体である。ソートアルゴリズムに不可欠のこの“計算”のコストが計算量に算入されていないので、一見計算が要らないように見えるというトリックがある。時間順に並んだ「バケツ」を用意してデータを出し入れしてくれている“裏方さん”がいるのである。
bashによる実装
使用例:
上の結果は正しい。
ところが処理系(Windows 10, Cygwin bash)で何度か実行しただけで、通常の数倍の時間経過したあと、たとえば以下のように一部追い抜きがあったり入力順そのままだったりと、誤った結果が出てくる例が見られた。