やねうらおさんによると、「広く知られているinsertion sortのコードは駄目すぎる」らしい。Wikipediaに載っているコード(2009.08.06版)を、
どこの馬鹿なアルゴリズムの教科書から引用してきたのかは知らないが、こんなものをサンプルとして掲載しないでもらいたい。
というのだから穏やかではない。
一連の劣悪なコードはこいつが犯人かも知れない。
と非難されてしまっている。
実際のところ、どのくらいの性能差になるのか、実験してみた。
C++の標準ライブラリ(std)のsortとWikipedia版、やねうらお版の比較。単位は秒。挿入ソートの2つ（つまりWikipedia版とやねうらお版）は、実行時間の比も計算した（1より小さい値はやねうらお版が速いことを意味する）。
size repetition std wiki yane y/w 4 1048576 0.3512 0.1576 0.1333 0.8459 8 233016 0.1148 0.06757 0.07265 1.075 16 65536 0.111 0.02996 0.1191 3.976 32 20971 0.1388 0.1141 0.09537 0.836 Timeout
codepadはすぐにタイムアウトしてしまうから、ベンチマークにはちょっと使えない（そもそも、ほかにどんなプロセスが動いているかわからないし）。
手元のCore i7 940 2.93GHz、主記憶9Gのマシンで実行してみる。
GCC 4.4.2（64ビット）の場合（コンパイルオプションは「-O3」のみ）
size repetition std wiki yane y/w 4 6291456 0.3001 0.1896 0.1957 1.032 8 1398099 0.1766 0.1374 0.1427 1.039 16 393216 0.1201 0.09756 0.09972 1.022 32 125829 0.1045 0.08267 0.08463 1.024 64 43689 0.08399 0.07897 0.08637 1.094 128 16047 0.07033 0.09022 0.1061 1.175 256 6144 0.06053 0.118 0.1466 1.243 512 2427 0.05325 0.1704 0.2192 1.287 1024 981 0.04746 0.263 0.3447 1.311 2048 405 0.04273 0.4241 0.5613 1.323 4096 168 0.03847 0.697 0.9245 1.326 8192 72 0.0356 1.187 1.582 1.333 16384 30 0.03148 1.978 2.623 1.326 32768 12 0.02696 3.157 4.208 1.333 65536 6 0.02857 6.37 8.425 1.323
配列のサイズが64くらいまでなら、std::sortを使うよりも挿入ソートのほうが速いようだ。その範囲では、Wikipedia版とやねうらお版にあまり差はない（Wikipedia版が若干速いか）。
インテルC++コンパイラ 11.0（64ビット）の場合（コンパイルオプションは「-fast」のみ）
size repetition std wiki yane y/w 4 6291456 0.2103 0.2164 0.2285 1.056 8 1398099 0.1464 0.1455 0.1447 0.9947 16 393216 0.107 0.106 0.1072 1.011 32 125829 0.1034 0.08955 0.09303 1.039 64 43689 0.08693 0.08898 0.09369 1.053 128 16047 0.07405 0.1059 0.1113 1.051 256 6144 0.06446 0.1456 0.1503 1.032 512 2427 0.05672 0.218 0.2219 1.018 1024 981 0.05066 0.3439 0.3462 1.007 2048 405 0.04571 0.5608 0.5618 1.002 4096 168 0.04118 0.9253 0.9255 1 8192 72 0.03799 1.578 1.579 1 16384 30 0.03406 2.628 2.629 1.001 32768 12 0.02887 4.197 4.208 1.003 65536 6 0.0307 8.464 8.46 0.9995
GCCのときよりstd::sortが速くなるのが早い。サイズ64ならもうstd::sortでよいようだ。GCCの場合より、std::sortが有利になるのが少し早い。Wikipedia版とやねうらお版にあまり差はない（やはり、Wikipedia版が若干速いか）。
Visual Studio 2008（32ビット）の場合（Releaseモード。オプションはデフォルトのまま）
size repetition std wiki yane y/w 4 6291456 0.329 0.184 0.171 0.9293 8 1398099 0.209 0.14 0.142 1.014 16 393216 0.136 0.114 0.111 0.9737 32 125829 0.105 0.1 0.098 0.98 64 43689 0.103 0.099 0.097 0.9798 128 16047 0.093 0.113 0.115 1.018 256 6144 0.083 0.141 0.155 1.099 512 2427 0.075 0.195 0.226 1.159 1024 981 0.066 0.295 0.35 1.186 2048 405 0.061 0.469 0.568 1.211 4096 168 0.057 0.77 0.937 1.217 8192 72 0.051 1.313 1.617 1.232 16384 30 0.045 2.207 2.72 1.232 32768 12 0.038 3.57 4.398 1.232 65536 6 0.04 6.966 8.513 1.222
配列サイズ64くらいまでは、挿入ソートがstd::sortより速い。その範囲では、Wikipedia版よりやねうらお版のほうが若干速いか。
いずれにしても、配列サイズが小さいなら、挿入ソートを試す価値はありそうだ。しかし、GNUやインテルのコンパイラをよく使う私には、挿入ソートの細かいチューニングは早すぎる最適化になりそうだ。
小さい配列限定のすごく速いソートなら、ソーティングネットワークはどうだろう。サイズ7の場合はこんな感じ(codepad)。batcherがソーティングネットワーク。単位は秒。codepadだと遅いか。
GCC 4.4.2（64ビット）では、ソーティングネットワークが速い。
std::sort: 0.411432 wikipedia: 0.3258 yaneurao: 0.331935 batcher: 0.28106
インテルC++コンパイラ 11.0（64ビット）の場合
std::sort: 0.324813 wikipedia: 0.331058 yaneurao: 0.298131 batcher: 0.228164
ここで使っている関数bathcersortは、CPANにあるAlgorithm::Networkで作った。次のようなコードでASCIIアートを描ける。
use Algorithm::Networksort qw(:all); $inputs=7; my @network = nw_comparators($inputs, algorithm => 'batcher'); print nw_graph(\@network, $inputs), "\n";
o--^--------^-----^-----------------o
| | |
o--|--^-----|--^--v--------^--^-----o
| | | | | |
o--|--|--^--v--|--^-----^--|--v-----o
| | | | | | |
o--|--|--|-----v--|--^--v--|--^--^--o
| | | | | | | |
o--v--|--|--^-----v--|--^--v--|--v--o
| | | | | |
o-----v--|--|--------v--v-----|--^--o
| | | |
o--------v--v-----------------v--v--o
仕組みを知りたいという向きにはKnuthの第3巻が、「サイズ7限定じゃ意味ないし、任意のサイズでできるようにしたらコンパイルできないじゃん」という向きには『LET OVER LAMBDA Edition 1.0』がおすすめ。
