マージソートアルゴリズムの解説
マージソートとは？
マージソートは、分割統治法（Divide and Conquer）を利用した効率的なソートアルゴリズムです。リストを小さな部分に分割し、個々の部分をソートしてから、それらを結合（マージ）して全体を整列させます。計算量は安定しており、最悪のケースでも O(n log n) です。この安定性と効率性から、特に大規模なデータセットに対して非常に有効です。
マージソートのステップ
- リストを半分に分割します。分割が不可能になるまでこの操作を繰り返します。
- それぞれの分割された部分を再帰的にソートします。
- ソートされた部分を2つずつマージし、1つのリストに結合します。
- すべての部分がマージされ、完全に整列されたリストが得られます。
マージソートのステップごとの変化
| ステップ | リストの状態 | アクション |
|---|---|---|
| 初期状態 | [5, 2, 9, 1, 5, 6] | — |
| 1 | [5, 2, 9] + [1, 5, 6] | リストを分割 |
| 2 | [5, 2] + [9] + [1, 5] + [6] | さらに分割 |
| 3 | [2, 5] + [9] + [1, 5] + [6] | 分割されたリストをソート |
| 4 | [2, 5, 9] + [1, 5, 6] | ソート後の部分をマージ |
| 5 | [1, 2, 5, 5, 6, 9] | 全体をマージ |
マージソートのJavaScript実装
// マージソートのJavaScript実装
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(left, right) {
let result = [];
while (left.length && right.length) {
if (left[0] < right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
return result.concat(left, right);
}
let array = [5, 2, 9, 1, 5, 6];
console.log("ソート前:", array);
console.log("ソート後:", mergeSort(array));
マージソートのPython実装
# マージソートのPython実装
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
while left and right:
if left[0] < right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
return result + left + right
array = [5, 2, 9, 1, 5, 6]
print("ソート前:", array)
print("ソート後:", merge_sort(array))
さらに詳しく
マージソートの大きな特徴は、計算量が安定して O(n log n) であることです。これは、データを再帰的に分割してソートするため、各ステップで n 回の比較が行われ、全体として log n ステップの処理が必要であるためです。このため、最悪計算量でも O(n log n) を維持できる非常に効率的なアルゴリズムです。
また、比較回数はリストの長さ n に比例しており、各ステップで n 回の比較が行われます。しかし、マージソートの欠点としては空間計算量が挙げられます。新たにリストを作成しながらマージを行うため、追加のメモリを必要とし、空間計算量は O(n) です。
まとめ
マージソートは、計算量が O(n log n) であり、最悪のケースでも効率よく動作するため、大規模データのソートに適しています。しかし、空間計算量が O(n) である点には注意が必要です。特に、メモリが限られている環境では、他のソートアルゴリズムと比較して検討することが求められます。