TimSort ~JavaやPythonに標準実装されている洗練されたソート法~ について勉強してみた（その１）

TimSortを勉強し始めたきっかけ

　当初、要素数$m$の集合における２つの要素からなるペア($m(m-1)/2$個のペア)のソートをしようと思っていて、ただでさえ$O(m^2)$のペア数があったので、これはソートを工夫しないと時間がかかるなと思い、自分でヒープソートを実装してソートしました。（ヒープソートは最悪$O(n\log n）\sim O(m^2 \log m^2 )$で実行。一方、素朴なバブルソートや挿入ソートは$O(n^2) \sim O(m^4)$かかる。ここではペアの数を$n \sim m^2$と記述）

しかし、思い返してみると、JavaやPythonだって日々進化しているので、標準実装に用いているソートアルゴリズムだって進化しているはずと思い、調べてみました。まさかバブルソートのような素朴なメソッドにとどめておく必然性があまり見当たらなかったので。

さすがさすが、日々精進されているだけのことはあって、非常に洗練されたソートアルゴリズムを実装していました。TimSortといいます。

TimSortを実装しているプログラム言語

• Python (2.3以降に標準ソートとして実装)
• Java (SE7以降に参照型配列用に標準実装)
• Swift

TimSortが実装され始めたのは、2002年でTim PeterによってPythonに実装されたのが初といいます。Tim Peterは、Pythonの有名な格言集である「The Zen of Python」の著者としても知られています。

(参考：Wikipedia　https://en.wikipedia.org/wiki/Timsort)

他、Android PlatformやGNU Octave, V8などにもTimSortは用いられています。

TimSortの概要

Gaurav SenによるTimSortの解説動画が非常にわかりやすかったですが
参考：https://www.youtube.com/watch?v=emeME__917E
インド英語が癖が強いことはご留意いただければと思います。（逆に日本人の英語はインド人からみれば相当癖が強くて聞き取れないようですが）この動画を主に参考にして勉強してきたことをここでまとめていきたいと思います。

TimSortの最悪計算時間

• $O(n\log n)$

です。ヒープソートやマージソート($O(n \log n))$などとあまり変わらないですが、これらよりも多少betterというところでしょうか。

TimSortの特徴を一言でいうと

イメージがつきやすいように乱暴な言い方をすると、

• 場合によってなるべくよいソート手法に自然にスイッチされるようにした、いいとこどりのアルゴリズム

といえるかと思います。

先ほど申しましたように、バブルソート$(O(n^2))$とヒープソート$(O(n \log n))$の比較のように、最悪計算時間の大幅な改善は見られませんが、それなりに改善されたソートアルゴリズムを組み合わせて、あらゆる場合にベストになるように工夫したものと言ってよいかと思われます。（かならずしもベストとはいいきれないと思いますが）

場合によって最善のソート方法を選ぶことは、プログラミング言語などのユースケースが多様なことが想定される場合に歓迎されるべきことと考えられます。多様なユースケースをカバーしようと思えば、データ数が大きい場合もあれば小さい場合もある。小さい場合にもより速いソート方法を提供しようというのがポイントだと勝手に思っています。

TimSortの手順概要

非常に粗い言い方をすると

1. ソートする対象の列を、ソート済みの小さな列（run）の集合にまとめる。
   　　●列にまとめる際には、小サイズではマージソートよりも効率的な挿入ソートを使う

2. runをマージソートを使ってマージするが、その際には
   　　●マージする回数を抑制できるようなrunのマージ順番を採用（フィボナッチ数に近い関係の不等式を用いたスタック）
   　　●効率的なマージ手順（範囲なし二分探索、ギャロップモード、隣り合うメモリ領域のマージなど）
   を用いて効率よく進めていく。

となるかと思います。以下、手順の詳しい内容を見ていこうと思います。

1. ソートする対象の列をすでにソートされた小さな列の集合「run」に分割する。

1-1. ソートされた小さな列「run」（要素数　32～64）

　まず、ソートする対象となる要素の列を受け取ったら、それをソート済みの小さな列「run」の集合にソートしながらまとめていくことを目指します。

　ここで、なぜ、サイズが32~64となるか？これは、挿入ソートが最速のソートアルゴリズムになるサイズの上限だからです。

1-2. 挿入ソートとその他アルゴリズムの比較

基本的なソート手法と考えられるものをまとめると以下の表のようになるかと思います。

平均的な計算時間	$O(n^2)$	$O(n\log n)$
手法	挿入ソート バブルソート　 選択ソート	マージソート クイックソート ヒープソート

一見すると、右側の$O(n \log n)$の手法を統一的に使えばよさそうですが、なぜ左側の挿入ソートを使うのでしょうか？（わかる人には愚問で申し訳ないです。）

この計算時間の見積もりは、$n$が十分大きい場合に有効ということを肝に銘じるべきです。データが大きいところでは、アルゴリズムの典型的な処理を繰り返す回数が効いてきますが、データ数が小さい場合にはデータ数に依存した因子よりも、アルゴリズムがどの程度複雑な処理をしているかどうかが効いてきます。それはデータ数に依存しない、アルゴリズム固有の処理の複雑さによるもので$O(1)$の項になります。おおむね、$O(n^2)$のアルゴリズムのほうが先に開発されており、１回の処理手順自体は単純なものなので、それらの$O(1)$の因子は小さくなります。

これはどういうことか？この見積もりの数をより細かく$O(1)$の係数因子$c_{i,b,s,m,q,h},\tilde{c}_{i,b,s,m,q,h}$も含めて表記し、考えてみましょう。

• $O(n^2)$手法

  • 挿入ソート: $c_i n^2 + \tilde{c}_i n$
  • バブルソート: $c_b n^2 + \tilde{c}_b n$
  • 選択ソート: $c_s n^2 + \tilde{c}_s n$

• $O(n \log n )$手法

  • マージソート: $c_m n \log n + \tilde{c}_m n$
  • クイックソート: $c_q n \log n + \tilde{c}_q n$
  • ヒープソート: $c_h n \log n + \tilde{c}_h n$

ここから下では$O(n\log n)$のアルゴリズムおよび、$O(n^2)$のアルゴリズムにかかる時間を競争させる際に単純化のためリーディングの共通因子である$n$をfactor outして比較してみたいと思います。この場合では、$n$が小さいところでは、それぞれがかかる最悪時間$f(n)$のふるまいは大雑把に以下のグラフのようになるととらえています。

データの大きさが小さいところでは、データの大きさとは無関係なさきほど導入した$O(1)$の因子が時間に効いてきます。基本的には$O(n^2)$のアルゴリズムの係数因子$\tilde{c},c_{i,b,s}$のほうが$O(n \log n)$のアルゴリズムの$c_{m,q,h}$,$\tilde{c}_{m,q,h}$よりも処理が単純なため小さくなります。いずれはデータが大きくなれば、$\log n$の微分係数が小さくなり、順番が逆転するのですが、データの大きさが小さいところでは、$\log n$関数の勾配となる$1/n$が十分に小さくないため、$O(n^2)$のアルゴリズムのほうが大きくなるまでにそれなりのインターバルがあるというのが私の理解です。

このように、データ小さい領域ではアルゴリズムがどの程度複雑な手順をしているかによって決定される$O(1)$の係数が効いてきます。となると、データが小さいときにはそのような係数が最も小さくなるような単純な処理を実施しているアルゴリズムを採用すべきとなります。それは答えを言うと、挿入ソートになります。（係数以外の見方として、挿入ソートのほうが、バブルソートや選択ソートよりも場合によって比較回数が削減できてしまうので（サボれる）、速くなります。現在は与えられた列のフルソートですので、部分ソートは考慮外とします。）

そこで、最初にソートされた部分列runを作るためには、挿入ソートが最速であるデータ数が保証されているうちは挿入ソートで作成していきます。それはおおむね**要素数32~64までといわれています。**そのため、runの要素数は32~64と設定されます。

1-3. 挿入ソートの改良

TimSortは、先ほど説明したようにデータが小さい段階では、挿入ソートを使用していますが、速い挿入ソートでもさらに速くしたいため、二分挿入ソートを用いています。二分挿入ソートは挿入位置を探索するために二分探索を実施する挿入ソートの改良アルゴリズムです。

1-4.runを生成する要素の局所性

ここでは、一つのrunを形成する際には、もとの与えられた列において近くに存在する要素同士でのみ挿入ソートをしてrunをくみ上げていきます。そのため、挿入ソートでは、runに挿入する要素を探索するためにサイズ$n$の列の要素をすべて探索するようなことはしません。よって、ソートのターゲットとなる列の要素数$n$が大きい場合、この操作にかかる時間のオーダーはrunの数の程度である$O(n)$程度で終了します。このオーダーはのちに出てくるマージソートにかかる時間に比べれば小さい項になり、最悪時間見積もりには効いてきません。

2. マージソートを使ってマージする。

2-1.いかに効率的にソート部分列を結合していくか？

結合回数をいかに減らして元のサイズの列を形成していくかが議論となります。そこで助けとなるのが、意外や意外、自然界の生物の成長と同じような規則性を利用することになります。それはフィボナッチ数列と呼ばれる数列です。この数列は生物、特に植物がぐんぐん効率よく成長していくパターンになっており、ぐんぐん生長するということはこれを採用すれば、効率よく短時間で大きな集合形成ができるということになります。

フィボナッチ数列は以下の漸化式で記述されます：

\begin{equation}
a_{m+2} = a_{m+1} + a_{m}
\end{equation}

この漸化式で最初の数項を$a_0 = 0, , a_1 = 1$としたときの$m \gg 1$のときのふるまいが

\begin{equation}
a_{m} \sim \frac{\phi^m}{\sqrt{5}}, \hspace{2cm} \phi = \frac{\sqrt{5} + 1}{2} \sim 1.6 > 1
\end{equation}

となります。このことから、対象となるサイズ$n$に成長するまで$m \sim \log n$の漸化式ステップで成長できることがわかります。

つまり、TimSortの狙いはフィボナッチ数列に近い構造でrunの結合処理を実施していけば、$\log n$のマージ回数で最終的なリストができるだろうというのが、ポイントです。

もちろん厳密なフィボナッチ数列にしてしまうとその構造にする際に手間がかかってしまい、また無駄骨です。厳密なフィボナッチ数列が欲しいわけではありません。ですから、フィボナッチ数列に近い構造に無理なく自然に近づいているようなマージプロセスを実施するということがポイントになります。最初はフィボナッチから遠くても、プロセスを実施していくうちにその数列に近づいていけばよいのです。オーダーの見積もりは$n \gg 1$の概算なので（$n$が大きくなったときにフィボナッチ的になればよい）。

それが次に説明する「フィボナッチ数列に近い不等式を用いたスタックの利用」になります。

2-2. フィボナッチ数列に近い不等式を併用したスタックの利用

runをスタックに入れながらマージします。（スタックの図は後日余力があれば追加しますが、しばらくはwikipediaのほうで参照してイメージをつかんでいただければ）

参照（スタック）：https://ja.wikipedia.org/wiki/%E3%82%B9%E3%82%BF%E3%83%83%E3%82%AF

スタックは基本的に入り口と出口が同じ一つのバケツのような構造をしており、その中には新しいデータは上から入れていって、上に積まれることになります。下のほうには古いメンバーが置かれている構造です。スタックからデータを取り出すときには、一番の上のデータから抽出されます。

ここで、スタックに入れてスタックの中で列をマージしていくのですが、データをすべて入れ終えて、マージの最終的な段階の手順に入るときに、スタックの中に入っているrunのサイズの関係式が以下の鏡モチのような関係を満たすように保持されることを目指します。ここでは、添え字の$0$はスタックの一番上のtop要素を示し、数字が大きくなるほど下にあるデータになります。ここで、runを表す記号を$r_{i} (i = 0, 1, \cdots)$とします。

\begin{align}
r_{n+2} &> r_{n+1} + r_{n} \\
r_{n+1} &> r_{n}
\end{align}

一番最初の式を見ていただければ、この関係式はフィボナッチ数列にはなりませんが、近い形をしていて、フィボナッチ列の緩和バージョンになっていると大雑把には見えます。この二つの不等式を満たしておけばフィボナッチ列に近いスタック内のデータ配列になっており、最終的なマージ手順は$\log n$で済むことになります。

残っている疑問はこのような不等式の状態に到達するようにするには、どのような処理をすればよいのかということです。それは、スタックにデータを入れるたびごとにスタックの器の上澄み部分で以下のような処理を実施することに相当します：（Javaっぽい、偽アルゴリズムをここに書きます。）
スタックの中のrunを要素に持つ配列をrunsという名前にします。topから昇順に配列のindexがつくと思ってください。

if(runs.length >= 2){
  if(runs[2].length > runs[1].length + runs[0].length){
    if(runs[1].length > runs[0].length){
       break;
    }
    else{
      merge(runs[0], runs[1]);
    }
 }
 else{
   merge(runs[1], min(runs[0], runs[2]));　//minはruns[0]とruns[2]のどちらか短い方を表すここだけのニセ記法
 }

}

上記のアルゴリズムでは、スタックに新しくデータを入れたときに上澄みの部分を不等式に近づけるようにマージ操作をしています。このような上澄みデータの継続的な操作は続けていけば結局のところ、最終的にフィボナッチ的なrunsの列を生成することにつながります。

これにはスタックという上からデータを流し込む構造が効いています。ここでのイメージはお好み焼きの溶かし切れていないダマだらけの生地を少しずつ鉄板の上に流し込みながら、下にある生地のほうが上側の生地よりも広い面積をとるように「へら」か何かでならしてくことに似ているかと思います。スタックにデータを流し込み始めた当初から、上澄みだけでも安定になるように下のほうが長くなるように「へら」で押しつけながら流し込む操作を続けていけば、下に沈みぱなしの古くからあるデータ列は長い間マージ操作で押さえつけられるので、ベターと長い列になっていき、安定した鏡餅状態のフィボナッチ数列状のrunの列が自然とできるようになります。つまり、古くからあるデータは下のほうに淀むスタックの性質が有効に働き、マージ操作に長期間さらされた要素数の大きくなったrunは自然にスタックの下に沈んでいることになることがキーです。

このように無理のないようにフィボナッチ状態のrunのデータ集合を構成して、マージの操作回数は$\log n$に抑えられることになりました。

2-3. マージソートの手法とマージソート１回あたりの最悪時間

あとは、マージソート１回の最悪計算時間が重要になってきます。実は、このすでにソートされたrunのおかげで、１回あたりのマージソートの実行時間は$O(n)$に抑えることができます。

マージソートでは、マージしたあとの配列を収めるメモリ領域を（もともと2つのrunが使っている連続したメモリ領域）まず保持しておいて、そこのメモリ領域に、２つのrunの合わせた要素の中で小さいものから順番に入れていくことをします。まず、2つのrunを比較する側Aと比較される側Bとして名前を付けます。比較する側Aはまず、小さい方から順番に「比較にかかるAの要素」として順次１つずつピックアップしていきます。(runはすでにソートされているので、このピックアップにかかる時間はO(1)です。)その一つの要素は、Bの最小の要素から順番に比較していきます。(ここでも、最小の要素からピックアップすることについても、ソートされていることが効いているので、まったく時間がかかりません。) ここで、比較して小さい方を配列を収めるメモリ領域に入れていきます。もしBの要素の小さければ、「比較にかかるAの要素」はそのままで、その小さいほうのBの要素をいれます。そして、Bにある次に小さい要素とそのAの要素を比較して、同様にマージした配列を収めるメモリ領域にAかBのどちらか小さいほうの要素を収めていきます。もし、「比較にかかるAの要素」が小さければ、それをメモリ領域に収めて、次に小さいAの要素を持ってきます。そして、メモリに入っていないBの要素で最も小さいところから比較を始めていきます。（ここら辺の詳細は非常に長くなるので、図や具体例を用いた説明はまた続編に記載しようかと思います。）ここでのポイントは、**すでにソートされているので、かかる時間は比較の回数分程度になり、それはマージソートされた領域に入る要素の数に等しくなる（比較と同時に入れるから）。つまり最悪でもかかる時間はO(n)**ということになります。

これらの計算から、TimSortの最悪計算時間は、一回あたりの計算時間$O(n)$に結合回数$O(\log n)$をかけて$O(n \log n)$程度になるだろうと考えられます。

2-3-1. 二分探索を使えばいいんじゃないか？

上記の説明は線形探索で説明していて、それはあまり効率が良くないんじゃないかという突っ込みが出てくると思います。しかしながら、**これはケースバイケースで、場合によっては二分探索のほうが時間がかかる場合があります。**たとえば、２つのrunが似たサイズで、片方の要素ともう片方の要素がお互いに近い値にあるような場合です。このような場合では、二分探索を実施すると、まったく大小関係を考慮しなくてもよいような大きさが全く違う相手との比較も実施してしまい、一つの要素に対して$\log n$の回数実施していきます。それをすべての要素に対して実施すると概算すると最悪の場合、$O(n \log n)$かかってしまいます。ですから、安直な二分探索は実施しないほうがよくなります。 それをするくらいなら、すでにソートされたrun同士のマージにおいては線形探索のほうが効率がよいことになります。

とはいえ、逆に２つのrunのうち、サイズに偏りがあったり、要素の大きさの分布に偏りがある場合には、線形探索をしても明らかに無駄な探索が存在して、それらをスキップしたほうが良いはずと思うのは当然です。例えば、run Aの最小値aよりも小さい値の要素がrun Bに多数ある場合、run Aの最小値aとrun Bの要素の大小比較を最小値から順番にやっていくことに無駄は生じるので、何らかのスキップを実施する手法が求められます。

それを効率よくやってくれるのが、範囲なし二分探索になります。これにより、要素の偏りが少なく線形探索のほうが効率が良い場合と二分探索のほうが効率が良い場合の橋渡しが可能になります。

2-3-2. 範囲なし二分探索

英語では、exponential searchやgalloping searchなどと呼ばれていますが、以下のようになります。

ここでは、マージする２つのrunをA,Bとして、Aのマージされてない最小の要素を$A[0]$とします。これをrun Bの要素$B[i], ( i = 0, 1,2,3,4, \cdots)$と比較していきますが、

1. $B[0], B[1], B[3], B[7], B[15], \cdots B[2^{n} - 1] $とインターバルを２の指数ごとに増やしていったなかで$A[0]$がどこのレンジ$(B[2^{n}] \sim B[2^{n+1} -1])$に入るかを探す。

2. その入ったレンジの中$(B[2^{n}] \sim B[2^{n+1} -1])$で、$A[0]$がどこに入るか二分探索で探索する

という手順になります。

このやり方の優れているところは以下のように見えます。
基本的に線形探索のほうが効率よくなるような偏りの少ない２つのrunの組み合わせにおいては、まず、上記の探索で、おおむね$B[0] \sim B[1]$の間や、$B[1] \sim B[3]$の範囲の狭い間に$A[0]$が入る傾向が強いことです。そのような場合であれば、$A[0]$が早めに探索のレンジにひっかかってくれて、無駄に遠いところを探索することを防いでくれるようになります。（二分探索の最大の欠点）かつ、ひっかかったあとの対象となる$B[i]$のレンジが狭いので、そこから線形探索しようが二分探索しようが大差がなくなります。一方で二分探索のほうがよいというものであれば、かなり大きいインターバルである$(B[2^{n}] \sim B[2^{n+1} -1])　(n \gg 1)$に$A[0]$が入るべきなので、そのような場合は二分探索のほうが当然効率がよくなります。このように範囲なし二分探索は両方のケースをバランスよく考慮してあげていることになっているといえます。

基本的にはTimSortは「範囲なし二分探索」を通じて、線形探索と二分探索の自然な切り替えを実施しているという雰囲気です。そこでの切り替えの指標がギャロップモード閾値と呼ばれるものであるようです。その閾値はおおむね7で設定されているようです。これはマージする片方のrunの先頭（末尾）から連続した要素を何個その順番のままマージ後の配列にコピーできるか、その個数で判断しています。この値7よりも連続してコピーされる数が多ければギャロップモードと言って二分探索が積極的に実施されるようです。この数値7の基準は、7以下の場合であれば、線形探索のほうが速いという今までの結果からきているようです。

わざわざこのようなモードを設定した背景には、もし、要素の最小値や最大値付近でこのような２つのrunの傾向があった場合、双方のrunの他の中間の大きさの要素の並びにおいても同様の傾向があるだろうということから設定しているようです。

2-4. マージソートに使う、列のコピー用のメモリ

２つの列をマージソートでマージする場合には、どちらか片方の列のコピーをメモリ上に確保します。基本的に要素数$O(n)$のマージソートを実施するには、$O(n)$のメモリ領域を確保する必要があります。そのメモリ領域の確保がマージソートにおいてはオーバーヘッドとなって効いてきます。このオーバーヘッドを少なくして、より速くマージソートを実施するには、このメモリの確保領域を小さくするようにします。

TimSortにおいては、まず二つのrunがあった場合、**要素数の少ない方のrunのコピーを作成するようにします。**しかしながら、runの場合であれば、すでにソートされている列であるため、さらにメモリ領域の確保を小さくすることができます。どのようにするか？

まず、２つのrunの最小値の大きい方に着目します。その大きい方の要素を持つものを仮にAとします。それよりも小さい値の要素がAでないほうのrun Bに連続して並んでいれば、その部分列は何もいじらなくてもそのままそこにおいておけばよい。（これは以下で述べるように、連続したメモリ領域をマージすることが効いています。）その分はマージソートするとか以前にそのままおいておけばよいので、対象から外す。また、大きい方に関しても同様に実施します。そうすると、マージソートの対象となる実効的なrunのサイズは小さくなります。

上記のような連続列を探す際には先ほど述べたような「範囲なし二分探索」を実施します。

ですから、コピーに必要なメモリ領域は、マージされたあとの配列に連続してコピーされる最小要素、および最大要素の連続分だけ削減できることになります。そのようにしてオーバーヘッドを削減してより高速化を実施しているようです。

2-4-1. メモリの隣り合う領域のrun同士が結合している

基本的にrunをスタックに入れる際には、メモリの領域の隣り合う同志から順番に入れていきます。上記のマージのニセアルゴリズムを見ていただければわかるように、マージするrunはスタックの中のとなり合う同士でマージすることになります。このようなマージを続けていけば、マージするもの同士は、メモリの隣り合う領域同士でマージすることになります。

これは非常に好都合です。配列のような参照型の変数はメモリの構造自体を変えずにポインタを指すか指さないかです。しかも、それらがマージするときには余分な中間にあるポインタを外して、扱うサイズを変更するだけで、簡単に一つの配列として扱いやすくなります。（ソートの対象となる配列の要素の型はもともと同じなので）そうすれば簡単に大きなサイズの配列が誕生し、さらに配列の操作を簡単に実施できてしまうと予想できます。（ここに関しては突っ込みをいれていただければ。）

また、さらによいことに、runはすでにソートされている配列なので、以下のような好都合なことができてしまいます:

• メモリの前の領域にある配列において、後ろの配列の先頭よりも小さい要素からなる部分配列が存在すれば、その部分配列は本当に何もしなくてもソートされた状態として出来上がっている。
• 逆にメモリの後ろの領域にある配列において、前の配列の末尾の要素よりも大きい要素からなる部分配列が存在すれば、その部分配列は本当に何もしなくてもソートされた状態として出来上がっている。

このように、runのソート済みされているという性質とメモリが隣り合うという性質から、無駄な操作の節約が効果的に実施できてしまうだろうことが読み取れます。

最後に

TimSortを自分で腹落ちさせて理解するように、感覚的な言葉と直感的な計算を多用して説明を試みました。非常に厳格で、正確性を好む人にとってはもしかしたら眉を顰めるような記事になったかもしれません。ただ一方で、間違いを恐れるような姿勢で、自分の理解を構築しているコアの部分に踏み込めずに煙に巻いた専門用語の羅列になってもそれはそれでなにか私個人として不満が残るようになった気もします。

正確性があまりないような記事で苦情を持つ方もいらっしゃるかもしれませんが、書いていくうちに、時間と労力がつきたこともございますし、より的確な表現は続編および第２版以降で体力を蓄えてからということでご勘弁をいただければと思います。

また、かなり理解し腹落ちするまで時間を要したところもあり、おそらく理解不足で完全に間違った認識になった箇所もあろうかと思います。そのような点を見つけられたら、ご指摘ご指導のほど、なにとぞよろしくお願い申し上げます。