マージ ソートの謎を解く: ソートを分割して克服するための初心者ガイド

マージ ソートは、主に大規模なデータセットの並べ替え効率を向上させるために、1945 年に John von Neumann によって導入されました。フォン ノイマンのアルゴリズムは、分割統治法を使用して一貫性のある予測可能な並べ替えプロセスを提供することを目的としていました。この戦略により、マージ ソートは小規模なデータセットと大規模なデータセットの両方を効果的に処理でき、すべてのケースで O(n log n) の時間計算量で安定したソートを保証します。

マージ ソートは、分割統治 アプローチを採用しています。これは、配列をより小さなサブ配列に分割し、それらを再帰的に並べ替えてから、並べ替えられた配列を元にマージします。このアプローチでは、問題を管理可能なチャンクに分割し、各チャンクを個別に並べ替えて効率的に結合します。その結果、アルゴリズムは並べ替えのワークロードを分割することで、大規模なデータセットでも良好なパフォーマンスを発揮します。

再帰は、同じ問題の小さいバージョンを解決するために関数がそれ自体を呼び出すプロセスです。問題が直接解決できるほど単純な点に到達するまで問題を細分化し続けます。この点は基本ケースと呼ばれます。

以下は JavaScript での Merge Sort の実装であり、配列がどのように再帰的に分割およびマージされるかを示しています。

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);
}

マージ ソートの仕組みをより深く理解するために、配列 [38, 27, 43, 3, 9, 82, 10]

を使用したプロセスを見てみましょう。

ステップ 1: 再帰的除算 (mergeSort 関数)
配列は、各サブ配列の要素が 1 つだけになるまで、より小さいサブ配列に再帰的に分割されます。これは、mergeSort 関数の次の行によって行われます:

function mergeSort(arr) {
    if (arr.length <= 1) return arr;

これで再帰は停止します。

再帰的除算がどのように展開されるかを次に示します:

• 初期呼び出し: mergeSort([38, 27, 43, 3, 9, 82, 10])
  • 配列は中間点で分割されます。 [38、27、43] および [3、9、82、10]

• 前半:

  • mergeSort([38, 27, 43])
    • 中間点で分割: [38] と [27, 43]
  • マージソート([27, 43])
    • [27]と[43]に分割
  • サブ配列 [38]、[27]、および [43] は個別の要素になり、マージする準備ができました。

• 後半:

  • mergeSort([3, 9, 82, 10])
    • 中間点での分割: [3, 9] と [82, 10]
  • マージソート([3, 9])
    • [3]と[9]に分割
  • mergeSort([82, 10])
    • [82]と[10]に分割
  • サブ配列 [3]、[9]、[82]、および [10] をマージする準備ができました。

ステップ 2: ソートされた部分配列をマージする (マージ関数)
ここで、マージ関数を使用して、サブ配列をソートされた順序でマージし直します。

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);
}

マージプロセスの仕組みは次のとおりです:

最初のマージ (基本ケースから):

• [27] と [43] をマージ → 結果は [27, 43] になります
• [38] と [27, 43] をマージ → 結果は [27, 38, 43] になります

この時点で、配列の左半分は完全にマージされています: [27, 38, 43]。

2 番目のマージ (基本ケースから):

• [3]と[9]を結合 → 結果は[3, 9]になります
• [82] と [10] を結合 → 結果は [10, 82]
• [3, 9] と [10, 82] をマージ → 結果は [3, 9, 10, 82] になります

これで、右半分が完全にマージされました: [3, 9, 10, 82]。

ステップ 3: 最終マージ
最後に、2 つの半分 [27, 38, 43] と [3, 9, 10, 82] がマージ関数を使用してマージされます。

27 (左[0]) と 3 (右[0]) を比較します。 3 27 と 9 を比較します。結果に 9 を加えます。
27 と 10 を比較します。結果に 10 を加えます。
27 と 82 を比較します。結果に 27 を加えます。
38 と 82 を比較します。結果に 38 を加えます。
43 と 82 を比較します。結果に 43 を加えます。
右側の配列から残りの要素 82 を追加します。
完全にマージされソートされた配列は次のとおりです:
[3、9、10、27、38、43、82].

時間計算量: 最良、平均、最悪のケース: O(n log n)
詳しく見てみましょう:

除算 (O(log n)): 配列が 2 つの半分に分割されるたびに、問題のサイズが小さくなります。配列は各ステップで半分に分割されるため、これを実行できる回数は log n に比例します。たとえば、8 つの要素がある場合、それらを 3 回半分に分割できます (log₂(8) = 3 であるため)。

マージ (O(n)): 配列を分割した後、アルゴリズムは小さい配列を順番にマージして戻します。サイズ n の 2 つの並べ替えられた配列を結合するには、各要素を 1 回比較して結合する必要があるため、O(n) 時間がかかります。

全体の複雑さ (O(n log n)): 除算には O(log n) のステップがかかり、各ステップで n 個の要素をマージするため、合計の時間計算量はこれら 2 つの乗算、O(n log n) になります。

空間の複雑さ: O(n)
マージ ソートでは、マージ フェーズ中に要素を格納するために一時的な配列が必要となるため、配列のサイズに比例した追加のスペースが必要です。

他の並べ替えアルゴリズムとの比較:
QuickSort: QuickSort の平均時間計算量は O(n log n) ですが、最悪の場合は O(n^2) になる可能性があります。マージ ソートはこの最悪のシナリオを回避しますが、スペースが懸念される場合のメモリ内ソートでは、一般に QuickSort の方が高速です。
バブル ソート: マージ ソートよりもはるかに効率が低く、平均および最悪のシナリオの時間計算量は O(n^2) です。

実際の使用法
マージ ソートは、メモリに収まらないデータを効率的に処理するため、大規模なデータセットをディスクから並べ替える必要がある外部並べ替えに広く使用されています。また、並列コンピューティング環境でも一般的に実装されており、マルチコア処理を利用してサブ配列を個別にソートできます。

さらに、Python (Timsort)、Java、C (std::stable_sort) などのライブラリと言語は、ソート操作の安定性を確保するためにマージ ソートのバリエーションに依存しており、オブジェクトや複雑なデータ構造のソートに特に適しています。

結論
マージ ソートは、その安定性、一貫したパフォーマンス、および大規模なデータセットのソートに対する適応性により、理論的なコンピューター サイエンスと実際のアプリケーションの両方において基本的なアルゴリズムであり続けます。 QuickSort などの他のアルゴリズムは、特定の状況ではより高速に実行される可能性がありますが、Merge Sort は保証されている O(n log n) 時間の計算量と汎用性により、メモリに制約のある環境や、等しいキーを持つ要素の順序を維持するのに非常に貴重です。最新のプログラミング ライブラリにおけるその役割により、現実世界のアプリケーションでも関連性が保たれます。

出典:

1. Knuth、Donald E. The Art of Computer Programming、Vol. 3: 並べ替えと検索。アディソン・ウェスリー・プロフェッショナル、1997 年、158-160 ページ。
2. コーメン、トーマス H.、他。アルゴリズムの紹介。 MIT Press、2009 年、第 2 章 (マージ ソート)、第 5 章 (アルゴリズムの複雑さ)、第 7 章 (クイックソート)。
3. Silberschatz、Abraham、他。データベース システムの概念。 McGraw-Hill、2010 年、第 13 章 (外部並べ替え)。
4. 「ティムソート。」 Python ドキュメント、Python ソフトウェア財団。 Python のティムソート
5. 「Java 配列.sort」オラクルのドキュメント。 Java の Arrays.sort()

以上がマージ ソートの謎を解く: ソートを分割して克服するための初心者ガイドの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。