in-place merge sort を実装してみた

こちらの論文を参考に書きました。

http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=D04E90C1CB92030C1B92452FB9E192A0?doi=10.1.1.22.8523&rep=rep1&type=pdf

実装

さくっと実装をまずお見せします。

const mergeSort = (arr: number[], L = 0, R = arr.length) => {
  if (R - L <= 1) {
    return;
  }
  const mid = L + Math.floor((R - L) / 2);
  mergeSort(arr, mid, R); // Qをソート

  for (let r = mid; L < r; ) {
    if (r - L === 1) {
      // Pのサイズが1のときは愚直にバブルさせる
      for (let i = L; i + 1 < R && arr[i] > arr[i + 1]; i++) {
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
      }
      break;
    }
    const p1Size = L + Math.floor((r - L) / 2),
      p2Size = L + Math.ceil((r - L) / 2);
    mergeSort(arr, L, p1Size); // P1 をソート
    // P2 をワーキングエリアにしてソートしていく
    for (let i = p1Size, p1 = L, p2 = p2Size, q = r; i > 0; ) {
      if (q < R && arr[q] < arr[p1]) {
        [arr[p2++], arr[q++]] = [arr[q], arr[p2]];
        continue;
      }
      [arr[p1++], arr[p2++]] = [arr[p2], arr[p1]];
      i--;
    }
    // P1 + Q が新たなQとなるので、rを更新
    r = p2Size;
  }
};

なにをやっているのか

1. 配列を半分にわけ、左をP、右をQとする。
2. Q をソート
3. P をさらに半分にわけ、左をP1、右をP2とする。
4. P1 をソート
5. P2 を利用して P1 と Q をマージ(詳しくは後述)
6. マージすると、[P2, P1 と Q をマージしたもの] という並びになるので、P2 を新しいP、 P1+Q を新しい Q として3から繰り返す
7. P のサイズが1になったら愚直にバブルソートを行い終了

こんな感じで、作業スペースをつくることでうまく in-place でマージできます。

マージ処理について

マージはそこまで難しくないです。

1. P1 と Q の先頭の要素を比較する
2. 小さいほうと P2 の先頭の要素をスワップ(ただし、P1 と P2 のサイズが異なる場合、スワップするのはP2の最初から2番目の要素)
3. これを [P2, P1 と Q をマージしたもの] となるまで繰り返す

こんな感じです。

論文ではさらに賢いやり方が紹介されています(スワップ操作の計算量を落とすテクなど)。ただ、in-place マージソートの実装ができればいいやと思ってあんまりちゃんと読んでないです…