モダンJavaScript入門: 二つの配列をマージソートする方法

1. マージソートとは

マージソートは、高速なソートアルゴリズムの一つで、平均計算時間がO(n log n)となる分割統治法に基づくアルゴリズムです。配列を2つの部分配列に分割し、それぞれをソートした後、2つのソート済み配列をマージ（結合）することで全体をソートします。

2. マージソートのアルゴリズムとコード例

マージソートの基本的なアルゴリズムは以下の通りです。

配列を2つの部分配列に分割する。
各部分配列に対して同様の操作を適用する（これを再帰と呼ぶ）。
部分配列が1つまたは0つの要素になったら、その部分配列はソート済みとなる。
2つのソート済み部分配列をマージする。

JavaScriptによるマージソートのコード例は以下の通りです。

function mergeSort(array) {
    if (array.length < 2) {
        return array;
    }

    const mid = Math.floor(array.length / 2);
    const left = array.slice(0, mid);
    const right = array.slice(mid);

    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    const sorted = [];

    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            sorted.push(left.shift());
        } else {
            sorted.push(right.shift());
        }
    }

    return sorted.concat(left.slice()).concat(right.slice());
}

console.log(mergeSort([9, 2, 5, 6, 4, 3, 7, 10, 1, 8]));  // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

3. マージソートの応用例

マージソートは様々な問題に応用できます。ここでは、数値の降順ソート、オブジェクトのソート、文字列のソートの3つを例に挙げます。

3.1 数値の降順ソート

マージソートを利用して数値の降順ソートを行うことができます。

function mergeSortDesc(array) {
    if (array.length < 2) {
        return array;
    }

    const mid = Math.floor(array.length / 2);
    const left = array.slice(0, mid);
    const right = array.slice(mid);

    return mergeDesc(mergeSortDesc(left), mergeSortDesc(right));
}

function mergeDesc(left, right) {
    const sorted = [];

    while (left.length && right.length) {
        if (left[0] >= right[0]) {
            sorted.push(left.shift());
        } else {
            sorted.push(right.shift());
        }
    }

    return sorted.concat(left.slice()).concat(right.slice());
}

console.log(mergeSortDesc([9, 2, 5, 6, 4, 3, 7, 10, 1, 8]));  // [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

3.2 オブジェクトのソート

マージソートを利用してオブジェクトの配列を特定のキーでソートすることができます。

function mergeSortObjects(array, key) {
    if (array.length < 2) {
        return array;
    }

    const mid = Math.floor(array.length / 2);
    const left = array.slice(0, mid);
    const right = array.slice(mid);

    return mergeObjects(mergeSortObjects(left, key), mergeSortObjects(right, key), key);
}

function mergeObjects(left, right, key) {
    const sorted = [];

    while (left.length && right.length) {
        if (left[0][key] <= right[0][key]) {
            sorted.push(left.shift());
        } else {
            sorted.push(right.shift());
        }
    }

    return sorted.concat(left.slice()).concat(right.slice());
}

const objects = [{id: 1, name: 'John'}, {id: 3, name: 'Alice'}, {id: 2, name: 'Bob'}];
console.log(mergeSortObjects(objects, 'id'));  // [{id: 1, name: 'John'}, {id: 2, name: 'Bob'}, {id: 3, name: 'Alice'}]

3.3 文字列のソート

マージソートを利用して文字列の配列をソートすることができます。

function mergeSortStrings(array) {
    if (array.length < 2) {
        return array;
    }

    const mid = Math.floor(array.length / 2);
    const left = array.slice(0, mid);
    const right = array.slice(mid);

    return mergeStrings(mergeSortStrings(left), mergeSortStrings(right));
}

function mergeStrings(left, right) {
    const sorted = [];

    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            sorted.push(left.shift());
        } else {
            sorted.push(right.shift());
        }
    }

    return sorted.concat(left.slice()).concat(right.slice());
}

console.log(mergeSortStrings(['banana', 'apple', 'cherry', 'dragonfruit']));  // ['apple', 'banana', 'cherry', 'dragonfruit']

以上、二つの配列をマージソートする方法の基本的な理解と応用例について学びました。これからマージソートを用いた様々な問題解決にチャレンジしてみてください。

AIko Code Symphony