やったこと

TimSort

TimSortの不幸はTimSortと名付けられたことだと思う。
絶妙に最適化された内容とTimという作者の名前が付いているせいで、アルゴリズムの本質が分かりづらくなっている。
というか、ある意味ではTimSortというのはオリジナルの実装しか存在しないのではないようにも思える。
実際、どこまでがプログラム的な最適化で、どこまでがアルゴリズム的な本質なのかを上手く説明できる人はいないんじゃないかな‥‥と。
ここまで広まってしまったから、もはや作者のTim Petersでさえ本質を見極められなくなっている可能性は十分ある。

‥‥ということを、昨日書いたTimSortとして深さを制限したマージソートを公開している例を見ながら考えていた。

自分が思うTimSortの本質は、この辺り。

1. 昇順もしくは降順で最初から並んでいる部分をrunという名前で分割する
2. runの長さが足りないときは、二分挿入ソートを使って範囲を伸ばす
3. runをスタックで管理するが、上手くスタックの深さがlog nに収まるようにマージしていく
4. マージは短い側をコピーして長い側にマージしていくようにする
5. マージの際に、値の移動が片側に一定回数以上集中したら、移動元の側でgallopサーチをして、値をまとめて移動する

だけど、gallopサーチの部分の重要度はそこまで高くないかな(値にい偏りがある場合の最適化なので)、と思うので、Rustの実装はいい落としどころを付いている気がする。

Apex

なんか面白くなってきた。
やっていきたい(そんな時間はない)。