EN
JP
KRマージソートとは？JavaScriptで分割統治による高速ソートを実装する方法を解説
マージソートは、代表的な高速ソートアルゴリズムの一つです。バブルソート、選択ソート、挿入ソートのような基本的なソートアルゴリズムと比べると実装は少し複雑になりますが、大きなデータに対しても安定した性能を発揮しやすいという特徴があります。JavaScriptで配列を並び替える場合、実務では標準のArray.prototype.sort()を使うことが多いですが、マージソートの仕組みを理解しておくと、効率的なソート処理がどのように組み立てられているのかを学ぶことができます。特に、配列を小さく分けてから結果を統合する流れは、アルゴリズム学習において非常に重要です。
マージソートは、「分割統治法」と呼ばれる考え方を使います。これは、大きな問題を小さな問題に分割し、それぞれを解決してから結果を組み合わせる方法です。配列全体を一度に並び替えようとするのではなく、まず半分ずつに分割し、1要素の配列になるまで細かく分けます。その後、整列済みの小さな配列を順番に結合していくことで、最終的に全体を整列させます。本記事では、マージソートの基本、JavaScriptでの実装方法、マージ処理、計算量、安定ソートとしての特徴、学習時のポイントまで分かりやすく解説します。
1. マージソートとは？
マージソートとは、配列を半分ずつ分割し、最小単位まで分けたあと、整列しながら結合していくソートアルゴリズムです。英語ではMerge Sortと呼ばれ、分割統治法の代表的なアルゴリズムとしてよく紹介されます。たとえば、[5, 3, 8, 1]という配列がある場合、まず[5, 3]と[8, 1]に分け、さらに[5]、[3]、[8]、[1]のように1要素ずつになるまで分割します。1要素の配列はすでに整列済みと考えられるため、それらを比較しながら結合していくことで、整列済みの配列を作ります。
マージソートの重要なポイントは、分割そのものではなく、分割した配列をどのように結合するかにあります。2つの整列済み配列を受け取り、それぞれの先頭要素を比較しながら小さい値を順番に取り出していくことで、1つの整列済み配列を作れます。このマージ処理を何度も繰り返すことで、小さな整列済み配列が大きな整列済み配列になり、最終的に元の配列全体が並び替えられます。JavaScriptで実装すると、再帰、配列分割、結合処理をまとめて学べるため、アルゴリズム学習の重要なステップになります。
1.1 分割統治法の考え方
分割統治法とは、大きな問題を小さな問題へ分割し、それぞれを解決してから結果を統合する考え方です。マージソートでは、配列全体を一度に並び替えるのではなく、まず配列を半分に分け続けます。配列が1要素になるまで分割すれば、その小さな配列はすでに整列済みとみなせます。その後、整列済みの小さな配列同士を結合しながら、より大きな整列済み配列を作っていきます。この流れが、分割統治法の基本的な考え方です。
この方法の利点は、複雑な問題を扱いやすい単位に分解できることです。バブルソートや選択ソートのような基本ソートは、データ量が増えるとO(n^2)になりやすく、大きな配列では処理が重くなります。一方、マージソートは分割の深さがlog nになり、各段階で全要素をマージするため、全体としてO(n log n)で動作します。データ量が増えたときの性能差を理解するうえでも、分割統治法の考え方は非常に重要です。
1.2 マージソートの特徴
マージソートの大きな特徴は、安定した性能を発揮しやすいことです。最良ケース、平均ケース、最悪ケースのいずれでも、基本的にO(n log n)で動作します。これは、入力データがすでに整列されていても、逆順に並んでいても、処理の流れが大きく変わらないためです。クイックソートのようにピボットの選び方によって最悪ケースが悪化するアルゴリズムと比べると、マージソートは計算量が安定している点が強みです。
また、マージソートは安定ソートとして実装しやすいアルゴリズムです。安定ソートとは、同じ値を持つ要素の元の順序を維持するソートのことです。たとえば、同じスコアのユーザーを並び替えるときに、同点のユーザーは元の登録順のまま残したい場合があります。マージ処理で同じ値が出たときに左側の要素を先に追加するようにすれば、安定性を保ちやすくなります。ただし、追加配列を使うため、メモリ使用量が増えやすい点には注意が必要です。
1.3 学習するメリット
マージソートを学ぶメリットは、ソートアルゴリズムだけでなく、再帰、分割統治、配列の結合、計算量、安定ソートといった重要な概念をまとめて理解できることです。バブルソートや選択ソートと比べると実装は少し難しくなりますが、基本ソートを学んだ後の次のステップとして非常に価値があります。特に、なぜO(n^2)よりO(n log n)のアルゴリズムが大規模データに強いのかを理解するために、マージソートは良い教材になります。
JavaScriptでは、配列操作が頻繁に使われます。slice()で配列を分割し、concat()やpush()で結果を組み立てるマージソートの実装は、JavaScriptの配列操作に慣れる練習にもなります。実務でマージソートを自作する機会は多くありませんが、標準のsort()を使う場合でも、効率的なソートの考え方を知っていると、比較関数やデータ量に対する意識が高まります。アルゴリズムの基礎力を高めたい人にとって、マージソートはぜひ理解しておきたい手法です。
2. マージソートの動作手順
マージソートは、大きく分けて「分割」と「結合」の2段階で動作します。まず、配列を半分ずつに分割し、1要素の配列になるまで再帰的に処理します。1要素の配列はそれ以上並び替える必要がないため、整列済みとして扱えます。次に、分割された小さな配列を、値を比較しながら順番に結合していきます。この結合処理を繰り返すことで、最終的に全体が整列された配列になります。
マージソートを理解するときは、分割処理だけでなく、マージ処理をしっかり理解することが重要です。分割は配列を半分にするだけなので比較的分かりやすいですが、実際に並び替えが行われるのはマージ処理の部分です。2つの整列済み配列を受け取り、それぞれの先頭から比較して小さい値を結果配列へ追加していくことで、1つの整列済み配列を作ります。この仕組みを理解すると、再帰で分割された配列がどのように戻ってくるのかも追いやすくなります。
2.1 配列を分割する
マージソートでは、配列を中央で分割します。JavaScriptでは、Math.floor(array.length / 2)で中央のインデックスを求め、slice()を使って左半分と右半分を作れます。配列の長さが1以下になったら、それ以上分割する必要はありません。なぜなら、1要素の配列はすでに整列されていると考えられるからです。この終了条件があることで、再帰処理が無限に続くことを防げます。
配列を分割する処理は、マージソートの準備段階です。この段階では、まだ値の大小を比較して並び替えているわけではありません。大きな配列を扱いやすい小さな配列に分けているだけです。再帰に慣れていない場合は、[5, 3, 8, 1]のような短い配列を使い、どの順番で[5, 3]と[8, 1]に分かれ、さらに[5]、[3]、[8]、[1]になるのかを紙に書いて確認すると理解しやすくなります。
const numbers = [5, 3, 8, 1];const middle = Math.floor(numbers.length / 2);const left = numbers.slice(0, middle);const right = numbers.slice(middle);console.log(left); // [5, 3]console.log(right); // [8, 1]
2.2 整列済み配列をマージする
マージ処理では、2つの整列済み配列を1つの整列済み配列にまとめます。左の配列と右の配列の先頭要素を比較し、小さい方を結果配列へ追加します。追加した側のインデックスを1つ進め、再び先頭要素同士を比較します。この処理を繰り返し、どちらか片方の配列が空になったら、もう片方に残っている要素をすべて結果配列へ追加します。これにより、2つの整列済み配列から、1つの整列済み配列を作れます。
このマージ処理は、マージソートの中心です。分割によってできた1要素の配列は整列済みなので、まずそれらを2要素の整列済み配列へマージします。その後、さらに大きな整列済み配列へ結合していきます。left[i] <= right[j]のように<=を使うと、同じ値がある場合に左側の要素を先に追加できます。これにより、元の順序を維持しやすくなり、安定ソートとしての性質を保てます。
function merge(left, right) { const result = []; let i = 0; let j = 0; while (i < left.length && j < right.length) { if (left[i] <= right[j]) { result.push(left[i]); i++; } else { result.push(right[j]); j++; } } return result.concat(left.slice(i)).concat(right.slice(j));}
2.3 再帰で全体を処理する
分割とマージを組み合わせると、マージソート全体を実装できます。mergeSort()関数では、まず配列の長さが1以下かどうかを確認します。1以下であれば、その配列はすでに整列済みなのでそのまま返します。そうでなければ、配列を左右に分割し、それぞれに対して再びmergeSort()を呼び出します。左右の配列が整列された状態で返ってきたら、最後にmerge()で結合します。
このコードでは、mergeSort()が自分自身を呼び出しています。これが再帰です。再帰処理では、終了条件を必ず用意する必要があります。ここではnumbers.length <= 1が終了条件です。この条件があるため、配列は最終的に1要素まで分割され、その後マージ処理によって戻ってきます。最初は複雑に見えますが、小さな配列で処理の流れを追うと、分割してから結合するという構造が見えてきます。
function mergeSort(numbers) { if (numbers.length <= 1) { return numbers; } const middle = Math.floor(numbers.length / 2); const left = numbers.slice(0, middle); const right = numbers.slice(middle); return merge(mergeSort(left), mergeSort(right));}console.log(mergeSort([5, 3, 8, 1])); // [1, 3, 5, 8]
3. JavaScriptでマージソートを実装するポイント
JavaScriptでマージソートを実装するときは、元の配列を変更しない設計にしやすいという特徴があります。slice()で新しい配列を作り、merge()で新しい結果配列を返すため、元の配列を直接書き換えずにソート結果を得られます。これは、ReactやVueなどのフロントエンド開発で重要になるイミュータブルなデータ操作の考え方にも近いです。元データを保ったまま、並び替え後の新しい配列を作れる点は、マージソートの分かりやすい利点です。
一方で、マージソートは配列を何度も分割し、マージ処理でも新しい配列を作るため、メモリ使用量が増えやすいという注意点があります。学習用としては非常に理解しやすい実装ですが、巨大なデータを実務で扱う場合は、標準のsort()や最適化されたライブラリを使う方が現実的な場合もあります。マージソートを実装するときは、非破壊的で分かりやすい設計と、メモリコストのバランスを意識することが大切です。
3.1 元配列を変更しない
マージソートの実装では、元の配列を直接並び替えず、新しい配列を返す形にしやすいです。slice()は元の配列を変更せずに一部を取り出すため、分割された左右の配列は新しい配列になります。また、merge()でも結果用の配列を作って値を追加していくため、元配列そのものは変更されません。このように、マージソートは自然に非破壊的なソートとして書きやすいアルゴリズムです。
元配列を変更しない設計は、UI開発で特に重要です。Reactなどでは、状態として管理している配列を直接変更すると、予期しない表示不具合や再描画の問題が起きる場合があります。新しい配列を作って返すマージソートの考え方は、状態を直接変更せず、新しい状態を作るという発想と相性が良いです。実務では標準sort()を使う場合でも、元配列を守るために[...array].sort()のようにコピーしてからソートする習慣を持つと安全です。
const original = [4, 2, 1, 3];const sorted = mergeSort(original);console.log(original); // [4, 2, 1, 3]console.log(sorted); // [1, 2, 3, 4]
3.2 オブジェクト配列への応用
マージソートは、数値配列だけでなく、オブジェクト配列にも応用できます。たとえば、商品一覧を価格順に並べたり、ユーザー一覧を登録日順に並べたり、記事一覧をタイトル順に並べたりする場合です。そのためには、比較条件を固定せず、外から比較関数として渡せるようにすると便利です。compare(a, b)の戻り値を使って、どちらの要素を先に追加するかを決めれば、さまざまなデータ構造に対応できます。
比較関数を外から渡せる設計にすると、汎用性の高いマージソート関数になります。価格順なら(a, b) => a.price - b.price、日付順なら(a, b) => new Date(a.date) - new Date(b.date)のように使えます。ただし、実務では標準のsort()を使った方が簡潔なことが多いです。オブジェクト配列へのマージソート応用は、実務で必ず自作するためというより、比較関数と安定ソートの仕組みを理解するために役立ちます。
function mergeBy(left, right, compare) { const result = []; let i = 0; let j = 0; while (i < left.length && j < right.length) { if (compare(left[i], right[j]) <= 0) { result.push(left[i++]); } else { result.push(right[j++]); } } return result.concat(left.slice(i)).concat(right.slice(j));}function mergeSortBy(array, compare) { if (array.length <= 1) { return array; } const middle = Math.floor(array.length / 2); const left = array.slice(0, middle); const right = array.slice(middle); return mergeBy(mergeSortBy(left, compare), mergeSortBy(right, compare), compare);}
3.3 降順にする方法
マージソートで降順にしたい場合は、比較関数を逆にします。数値配列で昇順にする場合はa - bに相当する比較を使いますが、降順ではb - aに相当する比較を使います。比較関数の戻り値によって、マージ処理でどちらの要素を先に結果配列へ追加するかが決まります。つまり、マージソートでも標準のsort()と同じように、比較関数の設計によって昇順と降順を切り替えられます。
降順ソートは、ランキング、スコア一覧、売上金額の高い順、人気順などでよく使われます。マージソートの降順実装を試すことで、アルゴリズム本体を大きく変えなくても、比較条件を変えるだけで並び順を制御できることが分かります。これは、JavaScriptのソート全般に共通する重要な考え方です。学習時には、同じ配列を昇順と降順の両方でソートし、比較関数の違いによって結果がどう変わるか確認すると理解が深まります。
const scores = [80, 100, 60, 90];const sortedDesc = mergeSortBy(scores, (a, b) => b - a);console.log(sortedDesc); // [100, 90, 80, 60]
4. マージソートの計算量
マージソートの時間計算量は、最良ケース、平均ケース、最悪ケースのいずれもO(n log n)です。これは、配列を半分ずつ分割することで分割の深さがlog nになり、それぞれの階層で全要素をマージするためです。たとえば、配列を何度も半分に分けていくと、要素数が多くても分割の段数は比較的少なくなります。そして、各段階のマージでは全要素を一度ずつ処理するため、全体としてn log nの処理になります。
バブルソート、選択ソート、挿入ソートのような基本ソートは、平均的にO(n^2)になります。要素数が少ない場合は大きな差を感じにくいですが、データ量が増えるほどO(n log n)との違いは大きくなります。マージソートは、入力データの並びに左右されにくく、安定した計算量を保ちやすい点が強みです。一方で、追加の配列を使うため、時間だけでなくメモリ使用量も考える必要があります。
4.1 時間計算量
マージソートでは、どのような配列でも分割とマージの流れが大きく変わりません。すでに整列済みの配列でも、逆順の配列でも、基本的には半分に分割してから結合していきます。そのため、最良ケース、平均ケース、最悪ケースの時間計算量がいずれもO(n log n)になります。これは、入力データの状態によって性能が大きく変わるクイックソートなどと比べて、安定した特徴です。
この安定した時間計算量は、大きなデータを扱うときに重要です。基本ソートでは、データ数が増えると処理時間が急激に増えやすくなりますが、マージソートは比較的効率よく処理できます。ただし、JavaScriptの実務では標準sort()が最適化されているため、マージソートを自作する場面は多くありません。学習目的では、O(n log n)の代表例として理解しておくと、アルゴリズム比較の土台になります。
4.2 空間計算量
マージソートは、マージ処理で新しい配列を作るため、追加のメモリが必要になります。一般的に、空間計算量はO(n)とされます。これは、ソート対象の要素数に応じて、結果配列や分割された配列のためのメモリが必要になるという意味です。速度面では優れた特徴を持つ一方で、メモリ効率では注意が必要です。特に、巨大な配列を扱う場合は、追加メモリの使用量が無視できないことがあります。
JavaScriptで学習用に実装する場合、slice()やconcat()を使うとコードは読みやすくなりますが、その分新しい配列が多く作られます。実務で極端に大きなデータを扱う場合には、標準sort()を使ったり、データベースやサーバー側でソートしたりする方が現実的です。マージソートを学ぶときは、時間計算量だけでなく、空間計算量も合わせて考える習慣をつけると、アルゴリズムの理解がより実践的になります。
4.3 安定ソートとしての特徴
マージソートは、実装方法によって安定ソートにできます。安定ソートとは、同じ値を持つ要素の元の順序を維持するソートです。たとえば、同じ点数のユーザーが複数いる場合、ソート前の登録順や表示順を保ったまま並び替えたいことがあります。マージソートでは、マージ処理で左側と右側の値が等しいときに、左側の要素を先に結果配列へ追加することで、元の順序を維持しやすくなります。
この安定性は、オブジェクト配列を扱う実務的な場面で重要になることがあります。たとえば、商品を価格順に並べたとき、同じ価格の商品は元の登録順のまま表示したい場合があります。ランキングや日付順の表示でも、同じ値を持つデータの順序を保ちたいことがあります。JavaScriptの標準sort()は現代の仕様では安定ソートとして扱われますが、アルゴリズム学習としてマージソートを理解しておくと、安定ソートがなぜ重要なのかを具体的に理解できます。
5. マージソートを学ぶときのポイント
マージソートを学ぶときは、いきなり全体の再帰処理を完璧に理解しようとするよりも、まず「2つの整列済み配列を1つにまとめるマージ処理」から理解するのがおすすめです。マージ処理が分かると、分割された小さな配列がどのように整列済みの大きな配列へ戻っていくのかを追いやすくなります。マージソートの実際の並び替えは、分割ではなく結合の段階で行われるため、この部分を重点的に見ることが大切です。
次に、再帰の終了条件を確認しましょう。配列の長さが1以下になったらそのまま返すという条件があるからこそ、分割処理は安全に終了します。再帰に慣れていないと、関数が自分自身を呼び出す流れが分かりにくく感じるかもしれません。その場合は、小さな配列を使って、どこで分割され、どこで戻り、どの順番でマージされるのかを図にすると理解しやすくなります。
5.1 まずマージ処理から理解する
マージソートの本質は、整列済み配列を結合する処理にあります。たとえば、[1, 4]と[2, 3]という2つの整列済み配列がある場合、それぞれの先頭を比較します。1と2を比べて1を結果に入れ、次に4と2を比べて2を入れ、次に4と3を比べて3を入れ、最後に残った4を追加します。この流れによって、[1, 2, 3, 4]という整列済み配列が完成します。
このマージ処理を理解すると、マージソート全体の仕組みも見えやすくなります。分割された1要素の配列同士をマージし、2要素の整列済み配列を作り、それらをさらにマージして4要素、8要素と大きくしていくイメージです。再帰のコードだけを見ると難しく感じる場合でも、マージ処理を手で追うと、実際に何が行われているのか分かりやすくなります。まずは小さな配列で、比較と追加の順番を確認しましょう。
5.2 再帰の流れを図で追う
再帰処理は、慣れないうちは分かりにくいです。マージソートでは、配列を半分に分ける処理が何度も行われ、その後にマージ処理で戻ってきます。コード上ではmergeSort(left)やmergeSort(right)のように短く書かれていますが、実際には複数回の関数呼び出しが積み重なっています。どの配列がどの順番で分割され、どの順番でマージされるのかを図にすると、再帰の流れが理解しやすくなります。
たとえば、[5, 3, 8, 1]を使う場合、まず[5, 3]と[8, 1]に分かれ、さらに[5]、[3]、[8]、[1]になります。その後、[5]と[3]がマージされて[3, 5]になり、[8]と[1]がマージされて[1, 8]になります。最後に[3, 5]と[1, 8]がマージされて[1, 3, 5, 8]になります。このように図で追うと、再帰が「分割して戻る」処理であることが見えてきます。
5.3 実務では標準sortも理解する
マージソートを学んだうえで、実務では標準のArray.prototype.sort()を使うことが多いです。標準メソッドはJavaScriptエンジン側で最適化されており、通常の一覧表示やデータ処理では十分な性能を発揮します。また、コードが短く、チーム開発でも理解されやすいため、自作のマージソートを実務コードに入れる必要はほとんどありません。実務で重要なのは、比較関数を正しく書くこと、元配列を変更するかどうかを意識すること、データ型をそろえることです。
一方で、マージソートを学ぶことは、標準sort()をより深く理解する助けになります。効率的なソートがなぜ必要なのか、O(n log n)がどのような意味を持つのか、安定ソートがどのような場面で役立つのかを理解できるからです。自作アルゴリズムと標準メソッドの役割を分けて考えることで、学習と実務の両方に役立ちます。学習ではマージソートを実装して仕組みを理解し、実務では標準sort()を適切に使うという使い分けが現実的です。
おわりに
マージソートは、配列を分割し、整列済みの小さな配列を結合していく高速ソートアルゴリズムです。分割統治法の代表例であり、再帰、マージ処理、計算量、安定ソートといった重要な概念を学ぶのに適しています。基本ソートより実装は少し複雑ですが、処理の流れを分割と結合に分けて考えると理解しやすくなります。
時間計算量は最良ケース、平均ケース、最悪ケースのいずれもO(n log n)であり、基本ソートより効率的です。一方で、追加の配列を作るため、メモリ使用量は増えやすいという注意点があります。JavaScriptでは実務で標準のsort()を使うことが多いですが、マージソートを理解しておくことで、効率的なデータ処理やアルゴリズム設計への理解が深まります。
