JavaScriptで実装するマージソートとクイックソートの徹底解説

マージソート(Merge Sort)とは

マージソートは、分割統治法(Divide and Conquer)に基づいたソートアルゴリズムです。最悪計算量は O(n log n) と非常に効率的ですが、その代償として追加の O(n) のメモリ領域が必要になるという特徴があります。

ここでは、このアルゴリズムを2つの関数、mergeSort と merge を作成して実装していきます。

• merge(マージ) ― 2つの引数(部分的にソートされた2つの配列)を受け取り、要素を正しい順序で挿入しながら1つの配列に結合する関数です。
• mergeSort(マージソート) ― 配列の左半分と右半分に対して再帰的に自身を呼び出し、その結果を merge 関数で結合する関数です。実装を見れば理解が深まるでしょう。

まずは merge 関数から実装していきましょう。

merge 関数の実装例

function merge(left, right) {
    let mergedArr = [];
    let i = 0;
    let j = 0;
    // どちらかの配列の末尾に達するまでマージを続ける
    while (i < left.length && j < right.length) {
        if (compare(left[i], right[j])) {
            mergedArr.push(left[i]);
            i++;
        } else {
            mergedArr.push(right[j]);
            j++;
        }
    }
    // 例:left が [1, 2, 3, 5]、right が [4, 6, 7, 9] の場合、
    // 上のループは left 配列の末尾に達した時点で終了し、
    // right 配列に3つの要素が残る。
    // どちらかの配列の残りの要素を追加するため、
    // left の i 番目以降と right の j 番目以降を
    // マージ済み配列に連結する必要がある。
    return mergedArr.concat(left.slice(i)).concat(right.slice(j));
}

この関数は、2つのソート済み配列を受け取り、O(n) の時間で1つのソート済み配列にマージします。処理の詳細はコード内のコメントを参照してください。以下のように動作を確認できます。

実行例

let a1 = [1, 2, 3, 5];
let a2 = [4, 6, 8, 9];
console.log(merge(a1, a2));

出力結果

[1, 2, 3, 4, 5, 8, 9]

mergeSort 関数の実装

次に、この merge 関数を利用して配列全体をソートする mergeSort 関数を作成します。関数を拡張可能にするため、比較関数(comparator)を外部から渡せるよう、内部関数を外側の関数でラップする構成にします。

内部関数の実装例

function mergeSortInner(arr) {
    if (arr.length < 2) {
        return arr;
    }
    let mid = Math.floor(arr.length / 2);
    // 0番目から mid - 1 番目までの要素で配列を作成
    let left = arr.slice(0, mid);
    // mid 番目から最後の要素までの配列を作成
    let right = arr.slice(mid);
    // 左半分をソートし、右半分をソートし、
    // ソート済みの2つの配列をマージして返す
    return merge(mergeSortInner(left), mergeSortInner(right));
}

この関数は配列を2つに分割し、それぞれを個別にソートした後、マージされた配列を返します。

完全なコードとテスト

function mergeSort(arr, compare = (a, b) => a < b) {
    function merge(left, right) {
        let mergedArr = [];
        let i = 0;
        let j = 0;
        while (i < left.length && j < right.length) {
            if (compare(left[i], right[j])) {
                mergedArr.push(left[i]);
                i++;
            } else {
                mergedArr.push(right[j]);
                j++;
            }
        }
        return mergedArr.concat(left.slice(i)).concat(right.slice(j));
    }
    function mergeSortInner(arr) {
        if (arr.length < 2) {
            return arr;
        }
        let mid = Math.floor(arr.length / 2);
        let left = arr.slice(0, mid);
        let right = arr.slice(mid);
        return merge(mergeSortInner(left), mergeSortInner(right));
    }
    // 内部のマージソートを呼び出してソート済み配列を返す
    return mergeSortInner(arr);
}

// 動作テスト
let arr = [5, 8, 9, 12, -8, 31, 2];
// 昇順でソート
arr = mergeSort(arr);
console.log(arr);
// 降順でソート
arr = mergeSort(arr, (a, b) => a > b);
console.log(arr);

arr = [
    { name: "Harry", age: 20 },
    { name: "Jacob", age: 25 },
    { name: "Mary", age: 12 }
];
// 名前のアルファベット昇順でソート
arr = mergeSort(arr, (a, b) => a.name < b.name);
console.log(arr);
// 年齢の降順でソート
arr = mergeSort(arr, (a, b) => a.age < b.age);
console.log(arr);

出力結果

[ -8, 2, 5, 8, 9, 12, 31 ]
[ 31, 12, 9, 8, 5, 2, -8 ]
[
    { name: 'Harry', age: 20 },
    { name: 'Jacob', age: 25 },
    { name: 'Mary', age: 12 }
]
[
    { name: 'Mary', age: 12 },
    { name: 'Harry', age: 20 },
    { name: 'Jacob', age: 25 }
]

このように、比較関数を差し替えるだけで、数値の昇順・降順はもちろん、オブジェクトの特定プロパティによるソートにも柔軟に対応できます。

クイックソート(Quick Sort)とは

クイックソートは非常に効率的なソートアルゴリズムで、データの配列をより小さな配列に分割(partition)するという考え方に基づいています。大きな配列は2つの配列に分割されます。1つは基準値(ピボット:pivot)より小さい値を保持し、もう1つはピボットより大きい値を保持します。

クイックソートは配列を分割した後、生成された2つの部分配列に対して再帰的に自身を2回呼び出してソートを行います。平均計算量と最悪計算量が O(n²)(n は要素数)でありながら、実際には大規模なデータセットに対して非常に高速に動作することで知られています。

パーティション(分割)処理の仕組み

パーティション処理では、まず配列の最初の要素を選択します(ランダム化クイックソートではランダムな要素を選択)。そして、配列の残りの要素をこの要素と比較し、この要素より小さい値をすべて「ピボットインデックス」の左側へ、大きい値を右側へ移動させます。処理が終わった時点で、ピボット要素(最初の要素)は正しい位置に配置されることになります。

これは、ピボットより大きい要素がすべて右側に、小さい要素がすべて左側に存在するため、その要素が正しい位置に置かれるからです。このパーティション処理を左右の部分配列に対して再帰的に適用することで、ソートが完成します。

partition 関数の実装例

function partition(arr, low, high, compare) {
    let pivotIndex = low + 1;
    for (let i = pivotIndex; i < high; i++) {
        if (compare(arr[i], arr[low])) {
            // ピボットより小さい数値をスワップ
            swap(arr, i, pivotIndex);
            pivotIndex += 1;
        }
    }
    // ピボットを正しい位置に配置
    swap(arr, pivotIndex - 1, low);
    // ピボットの位置を返す
    return pivotIndex - 1;
}

function swap(arr, i, j) {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// 動作テスト
let arr = [5, 1, 10, 8, 9, 3, 2, 45, -6];
console.log(partition(arr, 0, arr.length, (l, r) => l < r));
console.log(arr);

出力結果

4
[ -6, 1, 3, 2, 5, 10, 8, 45, 9 ]

注目すべきは、5 の左側の要素はすべて 5 より小さく、右側の要素はすべて 5 より大きいという点です。また、5 のインデックスが 4 になっていることも確認できます。

QuickSort 関数の実装

クイックソートの本体は次のように実装します。要素数が1より大きいウィンドウ(範囲)がある場合、配列の low から high までに対して partition を呼び出し、返されたインデックスを使って配列の左半分と右半分に対して再帰的にクイックソートを実行します。

実装例

function QuickSort(arr, low, high, compare = (l, r) => l < r) {
    if (high - low > 0) {
        // 配列をパーティション分割
        let mid = partition(arr, low, high, compare);
        // 左半分を再帰的にソート
        QuickSort(arr, low, mid, compare);
        // 右半分を再帰的にソート
        QuickSort(arr, mid + 1, high, compare);
    }
}

// 動作テスト
let arr = [5, 1, 10, 8, 9, 3, 2, 45, -6];
QuickSort(arr, 0, arr.length, (l, r) => l < r);
console.log(arr);

出力結果

[ -6, 1, 2, 3, 5, 8, 9, 10, 45 ]

まとめ

マージソートは安定した O(n log n) の性能を持ち追加メモリを必要とするのに対し、クイックソートは追加メモリをほとんど必要とせず、実用上は非常に高速です。両アルゴリズムとも「分割統治法」という共通の考え方に基づいており、比較関数をカスタマイズすることで柔軟なソート処理を実現できます。用途やデータの特性に応じて使い分けることが、効率的なプログラミングの鍵となります。