マージソートを使用する

マージソート (merge sort) は、配列を半分に 分割 し、それぞれを再帰的にソートしてから、2つの すでにソート済みの列を1本にマージ（併合） することで全体を整列させる比較ソートである。分割の深さが O(log n) で、マージが線形時間なので、最悪でも O(n log n) で安定して動作する点が特徴である。

  1. 分割: 区間 [lo, hi] の中央 mid で左半分 [lo, mid] と右半分 [mid+1, hi] に分ける。要素が1つだけならそのままソート済みとみなす。
  2. 再帰: 左右それぞれに対して同じ手順を繰り返す。
  3. マージ: 左と右はそれぞれ昇順になっている前提で、先頭同士を比較しながら小さい方から確定させ、どちらか一方が尽きたら残りを順に連結する。結果は補助配列などに書き、a[lo..hi] へ写し戻す。
procedure merge_sort(A, lo, hi)
  if lo >= hi then
    return
  mid = floor((lo + hi) / 2)
  merge_sort(A, lo, mid)
  merge_sort(A, mid + 1, hi)
  merge(A, lo, mid, hi)

procedure merge(A, lo, mid, hi)
  i = lo
  j = mid + 1
  k = 0
  while i <= mid and j <= hi
    if A[i] <= A[j] then
      B[k] = A[i]
      i = i + 1
    else
      B[k] = A[j]
      j = j + 1
    k = k + 1
  copy rest of left or right slice into B
  copy B back into A[lo .. hi]

時間計算量は常に O(n log n)。マージ用に O(n) の追加記憶領域が必要で、多くの実装は 安定ソート（等しいキーの相対順序を保つ）である。インプレース志向のクイックソートと比べて余分なメモリは要するが、最悪時の挙動が予測しやすいため外部ソートの基礎にも使われる。

バブルソートの O(n²) と比べてデータが大きい場面では有利になりやすく、クイックソートの最悪 O(n²) と比べて時間計算量のわるい入力がない反面、補助配列など 余計なメモリ を使うトレードオフがある。