JavaScriptでマージソートを使って配列を再帰的にソートする方法

本記事では、数値の配列を受け取り、マージソート（Merge Sort）アルゴリズムを使ってその配列を昇順にソートするJavaScript関数を作成します。

マージソートとは

マージソートは「分割統治法」に基づく代表的なソートアルゴリズムで、大きく分けて次の2つの処理から構成されます。

• 再帰的な分割： 配列を半分ずつに分割していき、最終的に要素が1つの状態まで細分化します。
• 反復的な統合（マージ）： 分割された小さな配列同士を、大小関係を比較しながら正しい順序で結合していきます。

この手法により、平均・最悪ともに O(n log n) の時間計算量で安定したソートを実現できるのが特徴です。

実装例

それでは、実際のコードを見てみましょう。

const arr = [23, 4, 67, 32, 1, 7, 56, 5, 89];

// 再帰的に配列を分割する関数
const mergeSort = arr => {
    // 要素が1つ以下なら、そのまま返す（再帰の終了条件）
    if (arr.length < 2){
        return arr;
    }

    // 配列を中央で左右に分割
    const middle = Math.floor(arr.length / 2);
    const left = arr.slice(0, middle), right = arr.slice(middle, arr.length);

    // 左右それぞれを再帰的にソートし、結果をマージして返す
    return merge(mergeSort(left), mergeSort(right));
};

// ソート済みの2つの配列を結合する関数
const merge = (left, right) => {
    const res = [];

    // 両方の配列に要素が残っている間、先頭の小さい方を取り出して結合
    while (left.length && right.length) {
        if (left[0] <= right[0]){
            res.push(left.shift());
        }
        else{
            res.push(right.shift());
        }
    }

    // 残った要素をすべて追加
    while (left.length){
        res.push(left.shift());
    };
    while (right.length){
        res.push(right.shift());
    };

    return res;
};

console.log(mergeSort(arr));

コードのポイント

• mergeSort 関数は、配列の長さが2未満になった時点で再帰を終了します。これが再帰処理の終了条件（ベースケース）です。
• Math.floor(arr.length / 2) を使って中央位置を求め、slice() で配列を左右に分割しています。
• merge 関数では shift() を使って各配列の先頭要素を比較しながら取り出し、昇順に新しい配列へ詰めていきます。
• <= で比較しているため、同じ値があっても元の順序が保たれる安定なソートになります。

出力結果

上記のコードをコンソールで実行すると、次のように配列が昇順にソートされて表示されます。

[
    1, 4, 5, 7, 23,
    32, 56, 67, 89
]