ティムソート
ティムソートは、安定ソートアルゴリズムであり(同じキーを持つ要素の順序が保持されます)、バランスの取れたマージ(マージにより、同様のサイズの並びがマージされます)の実行に努めます。
並べ替えの安定性を実現するために、連続する並びのみがマージされます。 2つの連続しない並びの間に、並び内に同じキーを持つ要素が存在する可能性があります。これらの2つの並びをマージすると、等しいキーの順序が変更されます。この状況の例([]は順序付けられた並びです):[1 2 2] 1 4 2 [0 1 2]
バランスの取れたマージを追求するために、ティムソートは、スタックの最上位で3つの並び、 X 、 Y 、 Zを考慮し、不変条件を維持します。
|Z| > |Y| + |X|
|Y| > |X|
これらの不変条件のいずれかに違反した場合、 YはXまたはZの小さい方とマージされ、不変条件が再度チェックされます。不変条件が保持されると、データ内の新しい並びの検索を開始できます。 これらの不変条件は、バランスのためのマージの遅延、キャッシュメモリでの並びの新たな発生の活用、およびマージの決定を比較的簡単にすることの間の妥協点を維持しながら、マージをほぼバランスの取れたものとして維持します。
元のマージソートの実装はインプレースではなく、N(データサイズ)のスペースオーバーヘッドがあります。インプレースマージソートの実装は存在しますが、時間のオーバーヘッドが高くなります。落としどころとして、ティムソートでは、Nよりも時間オーバーヘッドと空間オーバーヘッドが小さいマージソートを実行します。
最初に、ティムソートは二分探索を実行して、2番目の並びの最初の要素が最初の順序付けられた並びに挿入される場所を見つけます。次に、同じアルゴリズムを実行して、最初の並びの最後の要素が2番目の順序付けられた並びに挿入される場所を見つけ、順序付けを維持します。これらの場所の前後の要素はすでに正しい場所にあり、マージする必要はありません。次に、2つの並びの残りの要素のうち小さい方が一時メモリにコピーされ、要素は大きい方の並びとマージされて、現在は空き領域になります。最初の並びが小さい場合、マージは最初から始まります。
最悪の場合、ティムソートでは n要素の配列をソートするために O ( n log  n ) {\displaystyle O(n\log n)} 回の比較が必要になります。入力がすでにソートされているときに発生する最良のケースでは、線形時間で実行されます。これは、ティムソートが適応型ソートアルゴリズムであることを意味します。
オブジェクト参照またはポインタのソートには、クイックソートよりも有利です。これらは、データにアクセスして比較を実行するために高価なメモリ間接参照を必要とし、クイックソートのキャッシュコヒーレンスの利点が大幅に減少するためです。
マージは、従来のマージソートのように左から右、または右から左の両方向で実行できます。