フラッシュ、フラッシュ、フラーッシュ！（死ね）
結城浩氏の日記でこんなん見つけた。
http://d.hatena.ne.jp/hyuki/20060225
フラッシュソートだそうです。新しいソーティングアルゴリズムでしょうか。こんなのあったんだ。知らなかった。
各言語で書かれたソースコードが
http://www.neubert.net/Flacodes/FLACodes.html
にあるので、早速Cで書かれたものを読んで見ました。
なんか、クイックソートに分布数えソースが混ざったような感じですね。
クイックソートでは、値が大きい方と小さい方の二つに分けますが、
フラッシュソートでは分布数えソートっぽいのを使って複数に分けます。
その後はクイックソートと同じです。（このリンク先のCのコードを見てみると、分けられる量によってフラッシュソートを続行するか、挿入ソートに切り替えるかにしていますが。）
早速書いてみました。
（配列をふんだんに使うんで今日はHaskellじゃなくてCです。）
（isortは淫サーションソートです。紙面節約のため省略します。）
1: #include <stdio.h>
2: #include <stdlib.h>
3: #include <string.h>
4:
5: // 定数
6: #define THRESHOLD 75
7: #define BACKET_SIZE 75
8:
9: // マグロ
10: #define POS(rate, min, v) *1;
29:
30: { int i;
31: for(i=0; i < n; i++) backet[POS(rate, min, a[i])]++;
32: for(i=1; i < BACKET_SIZE; i++) backet[i] += backet[i-1];
33: }
34:
35: { int moved = 0, ix = 0, flash = a[0];
36:
37: while(1) {
38: int i = --backet[POS(rate, min, flash)];
39: moved++;
40: if(i == ix) {
41: a[i] = flash;
42: if(moved >= n) break;
43: while(1) {
44: ix++;
45: if(backet[POS(rate, min, a[ix])] > ix) break;
46: }
47: flash = a[ix];
48: } else SWAP(a[i], flash);
49: }
50: }
51:
52: { int i;
53:
54: for(i=0; i < BACKET_SIZE - 1; i++) {
55: int n2 = backet[i+1] - backet[i];
56: if(n2 > THRESHOLD) fsort(a + backet[i], n2);
57: else isort(a + backet[i], n2);
58: }
59: }
60: }
61: }
悲しいことに、オリジナル（のint用の改変版）のやつよか微妙に遅いです。どこか可笑しいのかも・・・。
ベンチマークとってみると、マージソートより早かったです。
（要素数が少ないとマージソートの方が早かった。）
（うちのパソコンはちょっと古いので、要素数80000までしか試せない。）
このアルゴリズムの特徴ですが、ソートする対象は数値じゃないと駄目くさいです。
でも数値であれば不動小数点数もソート出来るので、素の分布数えソートより汎用性が高そうです。
・・・とはいっても、クイックソートやマージソートの地位を脅かすほどのものじゃない臭いですね。
OOだと数値じゃないものをソートする方が多かったり？しますからね。
まぁ、気が向いたら使ってみてはいかがでしょうか。
# at 2006/3/19 1:00
ソースにちょっとバカっぽいところがあったので、少し修正。オリジナルのソースに、aを振り分ける前に一番大きい要素と一番最初の要素（a[0]）を入れ替えているの部分があるのですが、これは一体何でしょうか。取り払ってみても何も変わらないのですがね・・・。
# at 2006/3/22 0:47
疑問解消。↑をしておくことで、必ず一番大きい要素a[nmax]はa[n-1]に来るようになる。そのお陰で、その後のインサーションソートで配列の終端のインデックスを意識する必要が無くなる。（そのお陰で、少し早くなる）
俺の実装の場合特殊なインサーションソートに依存していないので、その処理は不要。それと、本家のC版とJava版の実装が微妙に違うのですが・・・。これは一体どういうつもり(笑)なんでしょうか。
どうやら必ずしも再帰は必要ないようです。なので、上記の「クイックソートに分布数えソートが混ざったような〜」はあくまでC版の実装を指した感想になります。不注意ですみません。
*1:int)(rate * (double)((v) - min)))
11: #define SWAP(x, y) do {int t; t = x; x = y; y = t;} while(0)
12:
13: void fsort(int a[], int n) {
14:
15: int max, min;
16:
17: { int i;
18: min = max = a[0];
19: for(i=1; i < n; i++) {
20: if(a[i] < min) min = a[i];
21: else if(a[i] > max) max = a[i];
22: }}
23:
24: if(max != min) {
25: int backet[BACKET_SIZE];
26: double rate = (double)(BACKET_SIZE - 1) / (double)(max - min);
27:
28: memset(backet, 0, BACKET_SIZE * sizeof(int
