導入
逆にソートされた入力に対するMergesortの複雑さはo（n^2）であり、この状況に合わせてMergesortを最適化することによりTimsortが生成されます。平均的な複雑さはn*o（log n）、最良のケースはo（n）であり、最悪の場合はn*o（log n）です。ティムソートは安定性です。アイデアは、最初にソートされた列をパーティション化し、次にパーティションをマージすることです。これはMergesortステップと同じように見えますが、逆のデータと大規模なデータの最適化がいくつかあります。
マージソートの最適化のアイデア
マージのソートには、いくつかの最適化方法があります。
クイックソートと同様に、再帰コールを避けるために、並べ替えを使用するか、小さな配列に並べ替えを選択できます。
merge（）が呼び出される前に、[中mid]が[mid+1]以下であるかどうかを判断できます。もしそうなら、マージする必要はなく、配列はすでに注文されています。その理由は非常に簡単です。 2つのサブアレイはすでに注文されているため、[MID]は最初のサブアレイの最大値であり、[MID+1]は2番目のサブアレイの最小値です。 [Mid] <= a [Mid+1]の場合、配列は全体として順序付けられます。
時間コピー要素を補助配列に節約するために、元の配列と補助配列の役割を再帰コールの各レベルで交換できます。
merge（）メソッドのマージプロセスは、iとjが境界を通過したかどうか、つまりエッジの半分が使用されているかどうかを判断する必要があります。側面の半分が使い果たされているかどうかを検出するコードを削除する別の方法。具体的なステップは、配列Aの後半A []を下降順にaux []にコピーしてから、両端からマージすることです。配列{1,2,3}および{2,3,5}の場合、最初のサブアレイは通常どおりコピーされ、2番目は後ろから正面にコピーされ、aux []の最終要素は{1,2,3,5,3,3,2}です。この方法の欠点は、マージのソートを不安定なソートにすることです。コードの実装は次のとおりです。
void merge（int [] a、int lo、int mid、int hi、int [] aux）{for（int k = lo; k <= mid; k ++）{aux [k] = a [k];} // 2つの端から中央まで（int k = lo; k <= hi; k ++）if（aux [i] <= aux [j]）a [k] = aux [i ++]; else a [k] = aux [j-];}ティムソートのステップ
パーティション
分割のアイデアは、配列を1回スキャンし、連続した正のシーケンス（昇順でソートされている場合、正のシーケンスは昇順のシーケンスです）、または[厳密に]（並べ替えアルゴリズムの安定性を確保するため）（run）を使用することです。逆シーケンスの場合は、パーティション内の要素を逆にします。例えば
1、2、3、6、4、5、8、6、4パーティションの結果は
[1,2,3,6]、[4,5,8]、[6,4]
次に、逆シーケンスを逆にします
[1,2,3,6]、[4,5,8]、[4,6]
マージ
極端な例を考えてみましょう。たとえば、パーティションの長さは10000、10、1000、10、10、および10です。もちろん、最初に20、20、1000に10 10、20、1000に融合したいと考えています。左から右にマージすると、毎回アレイ10000と毎回少量の組み合わせを使用します。これは高すぎます。そのため、戦略を使用して、マージの順序を最適化できます。
例
javaでcomparabletimsort.sort（）を例にとって、ランスタックを使用して、マージする必要があるかどうかを判断します。
if（nremaining <min_merge）{int initrunlen = countrunandmakeascending（a、lo、hi）; BinarySort（a、lo、hi、lo + initrunlen）;戻る; }min_merge（32）未満をソートし、分割後にバイナリ挿入で直接並べ替えます
int minrun = minrunlength（nremaining）; do {//次のパーティションの開始位置を見つけ、また逆シーケンスint runlen = countrunandmakeascending（a、lo、hi）をフリップします。 //実行スタックでの実行がminrunよりも大きいことを確認してください。現在のパーティションが小さすぎる場合は、背面から要素を取り出してメイクアップします（runlen <minrun）{int force = nremaining <= minrun？ nRemaining：minrun; BinarySort（a、lo、lo + force、lo + runlen）; runlen = force; } // run stack ts.pushrun（lo、runlen）に走ります。 //マージする必要があるかどうかを判断します。私はスタックの上部から始めて、それがマージできないことを知っています// 1。 runlen [i -3]> runlen [i -2] + runlen [i -1] // 2。 runlen [i -2]> runlen [i -1] ts.mergecollapse（）; lo += runlen; nremaining - = runlen; } while（nremaining！= 0）; //残りのすべての実行をマージしてソートソートを完了しますassert lo == hi; //残りの実行ts.mergeforcecollapse（）; assert ts.stacksize == 1;より重要な機能を見ています
/ ***最後の2回のランの長さが前のランよりも長く追加されている場合は、中央の位置で実行を使用し、前面と背面の長さを短くしてマージしてマージします*前の2回のランの長さが2回のランより短く追加されてから、プライベートボイドmergeCollapse（） if（n> 0 && runlen [n-1] <= runlen [n] + runlen [n + 1]）{if（runlen [n-1] <runlen [n + 1]）n - ;融合（n）; } else if（runlen [n] <= runlen [n + 1]）{mergeat（n）; } else {break; // Invariantが確立されます}}