Blog
先日、TimSortというソートアルゴリズムが話題になりました。TimSortは、高速な安定ソートで、Python(>=2.3)やJava SE 7、およびAndroidでの標準ソートアルゴリズムとして採用されているそうです。
C++のstd::sort()よりも高速であるというベンチマーク結果1が話題になり(後にベンチマークの誤りと判明)、私もそれで存在を知りました。実際のところ、ランダムなデータに対してはクイックソート(IntroSort)ほど速くないようですが、ソートというシンプルなタスクのアルゴリズムが今もなお改良され続けていて、なおかつ人々の関心を引くというのは興味深いものです。
しかしながら、オリジナルのTimSortのコードは若干複雑で、実際のところどういうアルゴリズムなのかわかりづらいところがあると思います。そこで今回はTimSortのアルゴリズムをできるだけわかりやすく解説してみたいと思います(クイックソート、マージソート、ヒープソート、挿入ソートの知識を前提とします)。
概要
TimSortとは一言で言うと、"STLのIntroSortのマージソート版"です。もう少し正確に言うと、それ＋いくつかのヒューリスティックです。いくつかのテクニックの集合体ですので、これらどこまでをTimSortと呼称するのかは不明です。
IntroSort
IntroSortとは、クイックソートの改良です。クイックソートは非常に高速なアルゴリズムですが、いくつか弱点があることが知られています。
弱点の一つは最悪計算量です。ピボットの選択がうまく行われないと、要素数の2乗に比例した時間がかかってしまいます。いくつかの要素をサンプリングした上での中央値をピボットとすると、平均的なデータに対しては非常に良好な性能を示すことが知られていますが、それは最悪計算量を保証するものではありません。たとえば、特定の実装に対して2乗時間かかるようなデータを作ることは容易で、それを狙って攻撃することも可能です。
Introソートではそれに対処するため、再帰の深さが要素数の対数を超えるとヒープソートに切り替えます。これにより最悪計算量をO(nlogn)に抑えつつ、平均的なデータではクイックソートに匹敵する性能を達成しています。
もう一つの弱点は要素数の少ない場合です。少ない要素数(<32程度)では計算量のオーダが大きくてもシンプルでオーバーヘッドの少ない、挿入ソートや選択ソートのようなアルゴリズムのほうが高速になることが知られています。そこで、分割が進み要素数が減ってきたら、挿入ソートに切り替えます。
TimSort
マージソートは最悪計算量O(nlogn)の安定ソートで、クイックソートのような最悪計算量の問題は起こりません。しかし、要素数が少ない場合はオーバーヘッドによりクイックソートと同様に遅くなります。TimSortは通常のマージソートとは異なり、予めある程度のサイズのソート済み列（runと呼ぶ）に分割して、それからマージを行います。
runサイズの決定
runのサイズは挿入ソートが最速の範囲(<32)でなるべく大きくします。また、runの個数が2の累乗のとき、後段のマージフェーズが早く終わるので、[16, 32)の範囲で、runの個数が2の累乗になるものを選択します。
runへの分割
まず最初に、入力列を小さなソート済み列へと分解します。入力列を前から順番になめ、単調増加（<=）している最大の接頭辞を求めます。それがある程度大きければそれでひとつのrunとします。増加列のサイズが小さすぎる場合は、挿入ソートを用い拡張します。この際に行う挿入ソートは、前方の要素がソート済みなので、途中から行うことができます。
最初の2要素が降順になっていた場合、増加列ではなく減少列を求めreverseします。これによって挿入ソートの回数を減らすことができます。ここで注意するのは、減少列はstrict(>)でなければならないということです。これは安定性の為です。
入力列がソート済みの場合、このフェーズで一度データをなめるだけでソートが終わってしまうので大変高速です。
2分挿入ソート
TimSortでは単純な挿入ソートではなく、2分挿入ソートが用いられています。これは要素の挿入位置の決定のために、ソート済み部分を2分探索するものです。安定性を保つように挿入位置を選ぶ必要があることに注意します。
マージ
ある程度のサイズのrunが出来上がったので、これらをマージします。マージは通常通り2つずつマージします。これを効率良く行うために、スタックを用いてrunを管理します。前フェーズで作成されたrunはまずスタックに載せられ、次の不変状態を満たすようにマージされます。
- length[top] + length[top – 1] < length[top – 2]
- length[top] < length[top – 1]
これを満たすスタックの深さは、最大でも要素数の対数になります。また、小さい物同士がマージされるので、計算量O(nlogn)が保証されます（TimSortの場合、大抵ほぼ同じサイズのrunがマージされるので実用上でも高速だと思われます）。
2つのrunのマージ
TimSortでは2つのrunのマージにも工夫がなされています。
連続領域
TimSortでは、必ず隣り合ったメモリ領域をマージします。これは先のスタックの不変条件によるrunのマージを行えば自然に満たされます。隣あうメモリ領域をマージすると
- 前方の列のうち後方の列の先頭よりも小さいもの
- 後方の列の後ろの要素のうち、前方の列の最後の要素より大きいもの
のコピーを省くことができます。連続した領域の部分列だけマージすれば良いことになります。
範囲なし2分探索
スキップする要素を計算するためにも2分探索を利用します。ただし、通常の2分探索とは異なり、最初に範囲を固定せずに、次のような2ステップで探索を行います。
- 1, 2, 4, 8, … のように2の累乗番目の要素を、要素が大きくなるまで見ていく
- 求める要素がどの範囲にあるか求まるので（例えば、8番目の要素が大きいのなら、[4, 8)に求める要素がある）改めてその範囲で2分探索
マージにおいては、求めたい要素はかなり前方にあるはずなので、通常の2分探索より比較回数は減ると思われます（平均的なデータに対してはリニアサーチのほうが速いんじゃないかと私は思います）。
ギャロップモード
残りの部分のマージは通常通り、先頭の要素を比較してマージして行きますが、同じ列から連続してたくさん採用され始めたら（>=7）、ギャロップモードと呼ばれるモードに入ります。
ギャロップモードとは、片方の先頭の要素よりも小さい要素が他方の先頭にいくつあるかを、上記の範囲なし2分探索において求めるものです。同じ列からある程度以上連続した場合、もっとたくさん連続することが予想されるので、これが有効に働くのだと思われます。
まとめ
以上がTimSortのアルゴリズムになります。実質的にはマージソートそのものと言えるでしょう。ランダムなデータに対しては、IntroSortやC++のstd::stable_sort()と比べて速度に優位性があるわけではないようです2（std::stable_sort()もマージソート＋少要素での挿入ソート）が、ソート済みデータ、あるいはほとんどソート済みデータに対しては最初のrun作成およびギャロップモードでの大幅なスキップが期待できるので、実際のデータにそういう傾向があるのであれば良いパフォーマンスが得られる可能性があります。また、クイックソートのように最悪計算量が問題になることがないので、これを標準に採用するのはセキュリティーの観点から利点があるでしょう。
