広く知られているinsertion sortのコードは駄目すぎる - やねうらお−ノーゲーム・ノーライフ
以前、有名どころのソートアルゴリズムについて、
比較回数とメモリコピー回数をカウントしたことがある。
そのとき挿入ソートも調べたのだが、コーディングするときに
「無駄コピーが発生するケースがあるけど、比較的レアケースだろうし、今回はシンプルに書こうと思うからこれで行こう」
のように思ったことを、上の記事を見て思い出した。
当時のコードを引っ張り出して読んでみると、日本のWikipedia版とほぼ同じコードだった。
しかも、最後tmp変数を書き戻すとき普通にコピー回数としてカウントしている。
計算回数のカウントが目的だから速度的な最適化は必要ないとの意識で書いていたが、
カウントが目的だからこそ重要な、アルゴリズムの選定を誤っていたのだ。
実際にコードを書き直すと、当然だがソート済みのデータに関してはコピー回数が0になる。
長いランダムデータに対してはさほどインパクトがないけど、
挿入ソートの用途は、少数データのソートやソートの仕上げなので、
当然やっておくべき最適化だった。
Wikipediaに載せる例としては、やはりわかりやすさが重視されるところだとは思う。
1要素を退避させ、一気にデータを移動、退避させておいた要素を戻す、
そういう流れは多くの人がわかりやすいと感じるものだろう。
ただし、仮にほとんどの人のセンスが悪く、センスの悪い人にわかりやすい説明がある場合、
それでもセンスのいい人にわかりやすい説明を書くべきだと思う。
また、ダメなコードが広まる危険があるというだけでも、それを載せない理由にはなると思う。
アセンブラで挿入ソートを書くにはどうしたらいいか、
あるいは、自分が挿入ソートの方法で並べ替えをするにはどうしたらいいか、
そういうことをしっかり考えた上で、元記事にある「yaneurao's insertion sort」の
コードにダイブすれば、まさに自分が考えた手順と同じに処理が流れ、気持ちよく読める。
しかし、挿入ソートのやり方を知りたくて来た人は、コードが長くて読みたくないと思ってしまうだろう。
詰将棋でもそうだが、実際の難易度よりも、「解きたい！」と思わせるような形かどうかが、
解き手にとっての解きやすさに影響することがある。
もちろん、キャッチーな見た目のために内容がおろそかになっては本末転倒だが。
というわけで、Wikipediaがどうあるべきかは難しい問題なので、
とりあえず両方載せればいいと思う。
また、自分でも「ソートは難しそうだから」とアセンブラ化を自重していたが、
少なくとも自分の頭の中で行き詰まるまでは、考えるべきだと思い直した。
自分が元のコードに妥協した理由として、tmp = data[i];とdata[j] = tmp;の
字面が似ているので対称性を感じ、片方だけ削っても効果が薄いと思ったこともある。
しかし、アセンブラレベルで見れば前者は（ソート済みであっても）必要なメモリリードだが、
後者は若干コストが高いメモリライトである上に、不必要なケースがある。
VBで書いていたからなおさらだったのだが、変数tmpがレジスタでなくメモリに見えていたのがいけなかった。
