quick sortよりも高速でmerge sortのように安定しているソートアルゴリズムtim sort [勘違い]
<追記>ベンチマークプログラムに誤りがありました。ソート済のシーケンスに対してソートを掛けていました。ご指摘ありがとうございます＞ak氏
そんな夢のようなソートアルゴリズムがあるのかというと、あるらしいんです。それがtim sortと呼ばれるアルゴリズムです。
画期的（？）なソートアルゴリズム「Sleep Sort」：濃縮還元オレンジニュース｜gihyo.jp … 技術評論社
このあたりで拾ってきたネタですね。
merge sortを改良したアルゴリズムで、安定*1しており、しかも実行速度にも優れているとか。アルゴリズムの性能の評価は済んでいるらしく、CPythonやJDK7には既に導入済みのようですね。
ならば当然Perlのソートも…と考えるわけですが、まず評価のためにJavaのソースをC++にそのまま移植してみました。それがこれ（いちおうテスト済）：
https://github.com/gfx/cpp-TimSort/blob/master/timsort.hpp
オリジナルはこちら：
http://cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/raw_files/new/src/share/classes/java/util/TimSort.java
インターフェイスはC++の標準ライブラリstd::sort()/std::stable_sort()と同じです。
int/double/boost::rational
https://github.com/gfx/cpp-TimSort/blob/master/bench.cpp
# MacOSX Snow Leopard / Apple clang 2.0 (llvm 2.9)
$ clang++ -DNDEBUG -O2 -Wall -Wextra bench.cp -o bench
$ ./bench
int
size 100000
std::sort 0.12273
std::stable_sort 0.182555
timsort 0.021382
double
size 100000
std::sort 0.121308
std::stable_sort 0.221106
timsort 0.026283
boost::rational
size 100000
std::sort 3.60624
std::stable_sort 2.60706
timsort 0.319079</del>適当なベンチマークですがだいぶ高速ですね。以下の記事では、ランダムなデータだとmerge sortよりも劣るという結果ですが、こちらはC++なせいかそうでもないように見えます。
Java 7のArrays.sort(Object[])：柴田 芳樹 (Yoshiki Shibata)：So-netブログ
このアルゴリズム、かなり複雑なのでソラで書けそうもないのが欠点ですが、これだけ高速ならPerlに移植する価値はありそうです。
ベンチマークプログラムが誤っていたので再検討中...取り急ぎ修正してみると特に高速ではありません： https://github.com/gfx/cpp-TimSort/commit/392af11ea2dea47a93b705a5ef95994449766113
*1:この「安定(stable)」はソートアルゴリズムの用語で、同等のデータのソート前の並び順が、ソート後も保持されるという意味です。テストコードで示すと次のtest.cppのstabilityテストのような挙動を示すものです。 https://github.com/gfx/cpp-TimSort/blob/master/test.cpp#L157
