Merge sort

平均計算時間: O(n \log n)

安定ソート

JavaScriptによる実装

function merge(a, left, mid, right) {
  const aLeft = a.slice(left, mid);
  const aRight = a.slice(mid, right);
  let i = 0, j = 0;

  for (let k = left; k < right; k++) {
    if (i >= mid - left) {
      a[k] = aRight[j];
      j++;
    } else if (j >= right - mid) {
      a[k] = aLeft[i];
      i++;
    } else if (aLeft[i] <= aRight[j]) {
      a[k] = aLeft[i];
      i++;
    } else {
      a[k] = aRight[j];
      j++;
    }
  }
}

function mergeSort(a, left = 0, right = a.length) {
  if (left + 1 < right) {
    const mid = (left + right) / 2;
    mergeSort(a, left, mid);
    mergeSort(a, mid, right);
    merge(a, left, mid, right);
  }
}

const a = [7, 15, 1, 8, 11, 5, 13, 0, 2, 4, 6, 3, 12, 14, 9, 10];
mergeSort(a);

console.log(a);
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]