ソート2：マージソートとクイックソート

100万個の値をすべての組を比べて並べると約5,000億（500 billion）回の比較が必要ですが、マージソートなら約2,000万（20 million）回ですみます。

問題を分けて、半分ずつ解く

前のユニットの方法はリスト全体を一度に扱い、その代わりに約 n² 回の比較がかかります。このユニットの2つの方法は、分割統治法と呼ばれる別の作戦を使います。リストを小さな部分に分け、それぞれを同じ方法で並べてから、整列した部分を組み合わせるのです。分割は部分の値が1個か0個になるまで続き、値が1個のリストはもう整列しています。この方法は小さなリストに対して自分自身を呼び出すので、再帰的です（再帰はユニット6でくわしく見ます）。

マージソート：仕事はマージ（併合）の中にある

マージソートはリストを半分に分け、左半分を並べ、右半分を並べ、整列した2つの半分を1つにマージします。かしこいのはマージの部分です。整列した2つのリストは、先頭の値だけを見て組み合わせられます。2つの先頭を比べ、小さいほうを書き出して、その先へ進みます。片方のリストが空になるまでくり返し、もう一方の残りをそのまま写します。[1, 4, 7] と [2, 3, 8] のマージは、1（1対2）、2（4対2）、3（4対3）、4（4対8）、7（7対8）と進み、最後に8を写します。6個の値で比較は5回です。合わせてn個の値を持つ2つのリストのマージでは、比較が n − 1 回を超えることはありません。

function merge(left, right) {
  const out = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (right[j] < left[i]) out.push(right[j++]);
    else out.push(left[i++]);
  }
  return out.concat(left.slice(i), right.slice(j));
}

function mergeSort(a) {
  if (a.length <= 1) return a;          // 整列済み
  const mid = Math.floor(a.length / 2);
  return merge(mergeSort(a.slice(0, mid)), mergeSort(a.slice(mid)));
}

なぜこれが速いのでしょうか。半分にしていく様子を段として思い浮かべましょう。8個の値のリストは、4個のリスト2つ、2個のリスト4つ、1個のリスト8つと分かれます。8は3回半分にできるので、段は3つです。どの段でも、すべてのマージを合わせると各値に1回ずつふれるので、1つの段にかかる比較は多くても約n回です。段が log₂ n 個あるので、合計は約 n log₂ n 回です。100万個の値なら約2,000万（20 million）回で、組ごとに比べる方法の約5,000億（500 billion）回とは大違いです。ラボと同じように [38, 27, 43, 3] と [9, 82, 10] に分けると、リスト [38, 27, 43, 3, 9, 82, 10] の比較は14回です。上のコードは3個と4個に分けるので、13回です。

その代わりにメモリを使います。マージには出力を書く場所が必要なので、マージソートは入力と同じ大きさの2つ目のリストを使います。またマージソートは安定です。等しいと比べられる値は元の順番を保ちます。先頭どうしが等しいとき、マージは左のリストから取るからです。これは表をある列で並べたあとで別の列で並べるとき、たとえば市で並べてから名前で並べるときに大切になります。

クイックソート：ピボットのまわりで分ける

クイックソートは別の方法でリストを分けます。ピボットと呼ぶ値を1つ選び、ピボットより小さいものはすべてその前に、ほかはすべてその後ろに来るようにリストを並べかえます。この手順を分割（パーティション）と言います。これでピボットは最終的な位置に入り、両側は同じ方法で別々に並べられます。左側の値はどれも右側のどの値より小さいので、あとでマージする必要はありません。

ラボでは、各部分の最後の値をピボットにする、教科書によくある版を使います。[5, 1, 4, 2, 8] では、ピボットの8をほかの4つの値と比べますが、どれも小さいので8は末尾に残ります。次の部分 [5, 1, 4, 2] はピボット2を使います。小さいのは1だけなので、2回交換するとリストは [1, 2, 4, 5, 8] になります。[4, 5] はあと1回の比較ですみます。合計は比較8回、交換2回です。

ピボットが真ん中近くに入れば、分けるたびに問題は半分になり、クイックソートの比較はマージソートと同じく約 n log₂ n 回です。しかも2つ目の写しを使わず、元のリストの中で作業できます。けれども悪いピボットは痛手です。リストがすでに整列していてピボットがいつも最後の値なら、分けるたびに値が1つはがれるだけで、クイックソートの比較は約 n²/2 回に逆戻りします。[1, 2, 3, 4, 5] では10回で、選択ソートと同じです。実際のライブラリは、たとえばランダムに選んだり、3つの見本の値の真ん中を選んだりして、ピボットをもっとよく選ぶことでこれを避けています。