メモログ

塵が積もって山とならないメモのログ

Merge Sort in JavaScript

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の実装だと空間計算量的には良くない。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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要素の場合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
node sortTest.js bubbleSort,selectionSort,insertionSort,topDownMergeSort 10 true
---- bubbleSort ----
[ 6489, 8505, 29, 5467, 2480, 3854, 4478, 2629, 8693, 2504 ]
[ 6489, 29, 5467, 2480, 3854, 4478, 2629, 8505, 2504, 8693 ]
[ 29, 5467, 2480, 3854, 4478, 2629, 6489, 2504, 8505, 8693 ]
[ 29, 2480, 3854, 4478, 2629, 5467, 2504, 6489, 8505, 8693 ]
[ 29, 2480, 3854, 2629, 4478, 2504, 5467, 6489, 8505, 8693 ]
[ 29, 2480, 2629, 3854, 2504, 4478, 5467, 6489, 8505, 8693 ]
[ 29, 2480, 2629, 2504, 3854, 4478, 5467, 6489, 8505, 8693 ]
[ 29, 2480, 2504, 2629, 3854, 4478, 5467, 6489, 8505, 8693 ]
number of iterates: 44
sorting: 0.692ms
---- selectionSort ----
[ 6489, 8505, 29, 5467, 2480, 3854, 4478, 2629, 8693, 2504 ]
[ 29, 8505, 6489, 5467, 2480, 3854, 4478, 2629, 8693, 2504 ]
[ 29, 2480, 6489, 5467, 8505, 3854, 4478, 2629, 8693, 2504 ]
[ 29, 2480, 2504, 5467, 8505, 3854, 4478, 2629, 8693, 6489 ]
[ 29, 2480, 2504, 2629, 8505, 3854, 4478, 5467, 8693, 6489 ]
[ 29, 2480, 2504, 2629, 3854, 8505, 4478, 5467, 8693, 6489 ]
[ 29, 2480, 2504, 2629, 3854, 4478, 8505, 5467, 8693, 6489 ]
[ 29, 2480, 2504, 2629, 3854, 4478, 5467, 8505, 8693, 6489 ]
[ 29, 2480, 2504, 2629, 3854, 4478, 5467, 6489, 8693, 8505 ]
[ 29, 2480, 2504, 2629, 3854, 4478, 5467, 6489, 8505, 8693 ]
number of iterates: 45
sorting: 0.605ms
---- insertionSort ----
[ 6489, 8505, 29, 5467, 2480, 3854, 4478, 2629, 8693, 2504 ]
[ 6489, 8505, 29, 5467, 2480, 3854, 4478, 2629, 8693, 2504 ]
[ 29, 6489, 8505, 5467, 2480, 3854, 4478, 2629, 8693, 2504 ]
[ 29, 5467, 6489, 8505, 2480, 3854, 4478, 2629, 8693, 2504 ]
[ 29, 2480, 5467, 6489, 8505, 3854, 4478, 2629, 8693, 2504 ]
[ 29, 2480, 3854, 5467, 6489, 8505, 4478, 2629, 8693, 2504 ]
[ 29, 2480, 3854, 4478, 5467, 6489, 8505, 2629, 8693, 2504 ]
[ 29, 2480, 2629, 3854, 4478, 5467, 6489, 8505, 8693, 2504 ]
[ 29, 2480, 2629, 3854, 4478, 5467, 6489, 8505, 8693, 2504 ]
[ 29, 2480, 2504, 2629, 3854, 4478, 5467, 6489, 8505, 8693 ]
number of iterates: 33
sorting: 0.559ms
---- topDownMergeSort ----
[ 6489, 8505, 29, 5467, 2480, 3854, 4478, 2629, 8693, 2504 ]
[ 6489, 8505, 29, 5467, 2480, 3854, 4478, 2629, 8693, 2504 ]
[ 6489, 8505, 29, 2480, 5467, 3854, 4478, 2629, 8693, 2504 ]
[ 6489, 8505, 29, 2480, 5467, 3854, 4478, 2629, 8693, 2504 ]
[ 29, 2480, 5467, 6489, 8505, 3854, 4478, 2629, 8693, 2504 ]
[ 6489, 8505, 29, 2480, 5467, 3854, 4478, 2629, 8693, 2504 ]
[ 29, 2480, 5467, 6489, 8505, 3854, 4478, 2629, 2504, 8693 ]
[ 6489, 8505, 29, 2480, 5467, 3854, 4478, 2504, 2629, 8693 ]
[ 29, 2480, 5467, 6489, 8505, 2504, 2629, 3854, 4478, 8693 ]
[ 29, 2480, 2504, 2629, 3854, 4478, 5467, 6489, 8505, 8693 ]
[ 29, 2480, 2504, 2629, 3854, 4478, 5467, 6489, 8505, 8693 ]
number of iterates: 34
sorting: 0.817ms

10件くらいだと他のソートとあまり変わらない。再帰するオーバーヘッドがある分、挿入ソートの方が効率的と言われている。

10000件で実行すると以下のような感じ。マージソートはかなり速い。

1
2
3
4
5
6
7
8
9
10
11
12
13
node sortTest.js bubbleSort,selectionSort,insertionSort,topDownMergeSort 10000
---- bubbleSort ----
number of iterates: 49909120
sorting: 230.373ms
---- selectionSort ----
number of iterates: 49995000
sorting: 134.691ms
---- insertionSort ----
number of iterates: 24925812
sorting: 61.047ms
---- topDownMergeSort ----
number of iterates: 133616
sorting: 6.362ms

マージソートの実装は一般的にin placeではなく、空間計算量のコストがO(n)かかる。wikiにはそのコストを2/nにしたり、in placeな実装にするといった提案がいくつか掲載されている。

tiled merge sortでは、locality of referenceを最適にするためにサブ配列をS個（CPUのキャッシュに最適になる個数）の配列に分割するところでストップして、そのサブ配列をin placeな挿入ソートでソートするという

ヒープソートは処理計算量では同じO(n log n)である一方空間計算量はθ(1)のみ求められる。また、効率的に実装されたQuicksortはRAM-basedな配列をソートする場合、マージソートよりも効率的らしい。

Although heapsort has the same time bounds as merge sort, it requires only Θ(1) auxiliary space instead of merge sort’s Θ(n). On typical modern architectures, efficient quicksort implementations generally outperform mergesort for sorting RAM-based arrays.[citation needed] On the other hand, merge sort is a stable sort and is more efficient at handling slow-to-access sequential media.
https://en.wikipedia.org/wiki/Merge_sort#Comparison_with_other_sort_algorithms

以上。