マージソートアルゴリズム
分割統治法による安定で効率的なソートアルゴリズムを学ぼう
O(n log n)
時間計算量（保証）
O(n)
空間計算量
中級
難易度
安定ソート
特性
🔧 実行設定
配列:
[38, 27, 43, 3, 9, 82, 10]
要素数:
7
🔗
アルゴリズムを実行してください
左側の設定パネルから条件を設定し、「マージソート実行」ボタンを押してください
💻 実装例（JavaScript）
function mergeSort(arr) {
// ベースケース：要素が1個以下
if (arr.length <= 1) {
return arr;
}
// 配列を中央で分割
const mid = Math.floor(arr.length / 2);
const left = arr.slice(0, mid);
const right = arr.slice(mid);
// 再帰的にソートしてマージ
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
const result = [];
let leftIndex = 0;
let rightIndex = 0;
// 両方の配列に要素がある間
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] <= right[rightIndex]) {
result.push(left[leftIndex]); // 安定性を保つため等しい場合は左を優先
leftIndex++;
} else {
result.push(right[rightIndex]);
rightIndex++;
}
}
// 残りの要素を追加
return result
.concat(left.slice(leftIndex))
.concat(right.slice(rightIndex));
}
// 使用例
const unsortedArray = [38, 27, 43, 3, 9, 82, 10];
const sortedArray = mergeSort(unsortedArray);
console.log(sortedArray); // [3, 9, 10, 27, 38, 43, 82]