挿入ソートの話の途中経過

Atom/gcc -O3だとループ変数をj=iからj=i-1に変えるといった、本質的ではない変更でも20〜30%の速度変化が起こり得るようだ。これはiccで比較してみた方が良いかもしれない。それらを含めた印象としては

• Wikipedia版もやね版も最適化がよく効いている場合には大差ない。
• やね版の方が最適化に失敗することが少ないようだ。

というところ。

余談。

要素数の少ないソートを想定していたのか。巨大なソート済み配列への追加なら「当たり前だけど、二分検索＋memmoveの方が速いよなあ」という結論で終わろうと思っていたのに。