メモログ

Insertion Sort in JavaScriptからの引き続き。内容はMerge sortからの抜粋なので、詳細はそちらを参照。

マージソートには n 個の配列を、n 個のサブ配列（配列の中には 1 個の要素が入ってる）に分割していって、それぞれソートした 2 つの配列を結合して、結合した配列でソートを行う。そして結合した 2 つ配列を結合して、ソートする…ということを繰り返していく。

マージソートはトップダウンで行う実装とボトムアップで行う実装とがある。下の実装例はMerge sortの Top-down implementation をそのまま JavaScript に置き換えただけである。二つの配列を交互に使いまわしていく。ので、ちょっとわかりにくい。The Merge sort algorithm - Ben’s Blogにあるコードの方が見やすい。けど、マージを実行するたびに新しく配列を作成した上にそれを concat で渡すので、上記 URL の実装だと空間計算量的には良くない。

function topDownMerge(
  sourceArray,
  begin,
  middle,
  end,
  resultArray,
  showArray,
  count
) {
  let i = begin;
  let j = middle;

  for (let k = begin; k < end; k++) {
    if (i < middle && (j >= end || sourceArray[i] <= sourceArray[j])) {
      resultArray[k] = sourceArray[i];
      i = i + 1;
    } else {
      resultArray[k] = sourceArray[j];
      j = j + 1;
    }
    count.count++;
  }

  if (showArray) {
    console.log(resultArray);
  }
}

function topDownSplitMerge(
  sourceArray,
  begin,
  end,
  sortingArray,
  showArray,
  count
) {
  const length = end - begin;
  if (length < 2) {
    return;
  }

  const middle = Math.floor((end + begin) / 2);

  topDownSplitMerge(sortingArray, begin, middle, sourceArray, showArray, count);
  topDownSplitMerge(sortingArray, middle, end, sourceArray, showArray, count);

  topDownMerge(sourceArray, begin, middle, end, sortingArray, showArray, count);
}

function topDownMergeSort(array, showArray) {
  const count = {
    count: 0,
  };
  const workingArray = array.slice(); // copy array
  topDownSplitMerge(workingArray, 0, array.length, array, showArray, count);
  if (showArray) {
    console.log(array);
  }
  console.log(`number of iterates: ${count.count}`);
}

実行結果は以下のような感じ。スクリプトの全体はGistを参照。

配列が 10 要素の場合。

node sortTest.js bubbleSort,selectionSort,insertionSort,topDownMergeSort 10 true