lucille 開発日記 » Flash sort

http://www.neubert.net/FSOIntro.html I think flash sort algorithm( O(N) time complexity ) is one of the fastest sorting algorithm in the world. Flash sort というソートアルゴリズムが、なかなかよさげです。 紹介文には、『クヌースは「その場での(in-situ, つまり extra なメモリ領域がいらない)ソートアルゴリズムは、平均して O(n log n) 時間を要するだろう」という予測をしたが、しかしこれはもうハズレである。新しいアルゴリズムであるこのフラッシュソートは、 O(n) 時間のその場でのアルゴリズムである』とあるくらいですから、なんとも”スゴ味”が伝わってきます。 ソートのアルゴリズムといえば、 o クイックソート(+ 挿

[nirvash]

『クヌースは「その場でのソートアルゴリズムは、平均して O(n log n) 時間を要するだろう」という予測をしたが、フラッシュソートは、 O(n) 時間のその場でのアルゴリズムである』