JavaScriptで学ぶアルゴリズム③［ソートアルゴリズム⑵］-マージソート

外資系企業でソフトウェアエンジニアをしております、タロイモと言います。今日もよろしくお願いします。

前々々回から、O(n)とO(1)、O(log n)、O(n^2)アルゴリズムの紹介をしてきました。

今回はO(n log n)のソートアルゴリズムの中でマージソートを紹介します。

O(n log n)

以下の図を見て分かるとおり、O(n log n)はアルゴリズムとしてはあまり優れていません。

ただソートアルゴリズムはO(n^2)とO(n log n)しかないため、順番に並んでないバラバラなデータのときは、このO(n log n)アルゴリズムが最速になります。

マージソート

ソートしたいデータ列を、同じ長さの2つのデータ列に分割します。データ列の中身が1個になるまで分割したら、各データ列をマージ（統合）していき、1つの整列済みデータ列にしていきます。

画像で表すと以下のような流れになります。

▼分割

①まずはデータ列を限界まで分割します。

▼マージ

②この1個のデータ列をまたマージしていきます。このマージをする際にソートし、小さい順に順番を変えていきます。
今回は一番右の5,6だけ順番が変わりました。

③次に、マージしたグループの先頭の数字（一番小さい数字）を比較し、
小さい方を新しいグループに移動します。

左側のグループは1 < 2なので1を移動し、 右側のグループは3<5なので3を各グループに移動します。

④また、残りのデータの列の先頭を比較し、、
どんどん新しいグループに小さい順に並べていきます。

左側のグループには2 < 8なので2を移動、右側のグループには 4 < 5なので4を移動。

⑤次にまた、各グループの先頭の数字を比較し、小さい方の数字から新しいグループにマージしていきます。

1 < 3なので1を新しいグループに入れる。

次にまた、先頭を比較して、2 < 3なので2を新しいグループに入れる。

これらの先頭の比較を繰り返して、、、

以下のように小さい順に並び替えることができます。

以上がマージソートです。

マージソートはデータを分割する時間はかかりません。
格段はn個データがあるので、格段の計算時間はnになります。
今回で言えば、格段には8個のデータがあるので、格段の計算時間は8です。
また、n個のデータを1個になるまで分割していくと、
分割した段の数はlog n段あることになります。
今回で言えば、log8なので分割した段は3段ありますね。

格段のデータ数×格段の数が計算時間になるので、
n × log nでO(n log n)という計算量オーダーとなります。

JavaScriptで表すと

マージソートをJavaScriptで表すと以下のようになります。

let array = [1, 4, 3, 8, 7, 6, 2, 5];

//datas 並べ替えをする配列
function merge_sort(datas) {
 // 要素数
 const COUNT = datas.length;
 // 要素数が 1 以下の場合
 if (COUNT <= 1) {
   return;
 }
 // 中央の添字
 const CENTER = Math.floor(COUNT / 2);
 // 中央で分割した配列
 let leftData = datas.slice(0, CENTER);
 let rightData = datas.slice(CENTER);
 // 各配列のマージソート
 merge_sort(leftData);
 merge_sort(rightData);
 // 結合後の配列
 const mergedData = [];
 // 分割した配列の要素数
 let count1 = leftData.length;
 let count2 = rightData.length;
 
 let i = 0;
 let j = 0;
 
 // 両方の配列に要素がある間
 while (i < count1 && j < count2) {
   //比較する値
   let value1 = leftData[i];
   let value2 = rightData[j];

   if (value1 <= value2) {
     // value1とvalue2が等しい OR value1 が小さい場合
     mergedData.push(leftData[i]);
     i++;
   } else {
     // value2 が小さい場合
     mergedData.push(rightData[j]);
     j++;
   }
 }
 // leftDataに要素がある間
 while (i < count1) {
   mergedData.push(leftData[i]);
   i++;
 }
 // rightDataに要素がある間
 while (j < count2) {
   mergedData.push(rightData[j]);
   j++;
 }
 // 元の配列にソートした配列を当てはめる。
 for (let i = 0; i < COUNT; i++) {
   datas[i] = mergedData[i];
 }
}

merge_sort(array);

console.log(array); //[1, 2, 3, 4, 5, 6, 7, 8]

次回は、クイックソートを紹介いたします。

今回もご精読ありがとうございました。