アルゴリズム
ソート

ソートの本に最速のソートというのを載せています。
ネタ的には何らかの名前がついていると思うのですが、ちょっとわかりませんでした。

最速のソートとは、比較を使う他のソートアルゴリズムと比べて
・最悪パターンの比較数が最も少ない
・並び替えの為に使う読み込みと書き込みが最も少ない
という特徴を持つソートです。

時間計算量はO(n logn)、空間計算量はO(1)またはO(n!)です。

O(1)とO(n!)って天と地ほどの差がありますが、空間計算量の定義によります。
実際、プログラムが動き始めればメモリ使用量はごく僅かです。
しかし、その動かすプログラムのサイズがO(n!)です。

つまり、プログラムで二分木探索を行い、現在の配列がどの並び順かを特定し、
並び順がわかればそれを最も適した形で入れ替えてソートします。
4個の要素を並び替えるのなら、if文が4!-1=23個存在します。

もちろん、4個の並び替えに特化してますから、
8個を並び替えたいときは専用に別のプログラムを用意します。

で、こういうジョークソートを話していたら、プログラムを作ってくれる人がいました。
最速のソート

さて、実行結果ですが…超絶遅いです。
C++のstd::sortの方が何倍も早いです。

理由は、CPUキャッシュでしょう。
プログラムサイズが肥大化しているわけですから、
キャッシュ効率が超絶悪くなっていると思われます。

やはり時代を先取りしすぎたアルゴリズムでしたね。