ティムソートを使用する

ティムソート (Timsort) は、Tim Peters が Python の list.sort() 向けに設計した 安定 な比較ソートである。

マージソートの分割・併合の枠組みに、すでに整列している連続区間（ラン） を活かす仕組みと、短いランを伸ばす 挿入ソート を組み合わせた ハイブリッド アルゴリズムである。

Python 3 の組み込みソートや、Java のオブジェクト配列向け Arrays.sort など、実用の標準ソートとして広く採用されている。

  1. ランの検出: 配列を左から走査し、昇順 または 厳密な降順 の連続区間（ラン）を見つける。降順ランはその場で反転し、昇順ランにそろえる。
  2. ランの拡張: ランの長さが 最小ラン長 minRun 未満なら、二分探索付き挿入ソートで minRun まで（または配列末尾まで）伸ばす。minRun は配列長から計算され、おおむね 32〜64 付近になる（デモでは見やすさのため 4 に固定している）。
  3. スタックへの積み上げ: 整えたランを (開始, 長さ) としてスタックに push する。
  4. マージの抑制: push のたびに、スタック上のラン長のバランスを見て 隣接ランをマージ する。最後に残ったランをすべて併合して全体を整列する。
procedure timsort(A)
  n = length(A)
  minRun = compute_min_run(n)
  stack = empty list of runs
  i = 0
  while i < n
    runLen = count_run(A, i)
    if A[i .. i+runLen-1] is descending then
      reverse(A, i, i + runLen - 1)
    if runLen < minRun then
      extend_run_with_insertion(A, i, min(i + minRun, n) - 1)
      runLen = min(minRun, n - i)
    push stack with (i, runLen)
    merge_collapse(stack, A)
    i = i + runLen
  merge_force_collapse(stack, A)

マージ自体はマージソートと同様に 2 本の昇順列の先頭を比較しながら確定させる。実装では ガロップ（一方の列が連続して勝つときにまとめて取り込む）などの最適化も入るが、デモでは基本的な 2 路マージまでを追えるようにしている。

最悪時間計算量 は O(n log n)。すでに昇順に近い入力ではランが長く取れ、最良は O(n) に近づく。安定ソート であり、等しいキーの相対順序を保つ。補助領域はマージ用に O(n) が必要になることが多い。

クイックソートのように最悪 O(n²) に落ちにくく、マージソートのように 安定 で O(n log n) を保てる点が実データ向けの強みである。一方でラン管理やマージ用バッファなど実装は重く、教育用の最小例としてはマージソートや挿入ソート単体のほうが追いやすい。ティムソートは「実世界の偏りのある入力でも速く・安定に」という目的で標準ライブラリに組み込まれるタイプのソートである。