Merge Sort wurde 1945 von John von Neumann eingeführt, hauptsächlich um die Effizienz beim Sortieren großer Datensätze zu verbessern. Von Neumanns Algorithmus zielte darauf ab, mithilfe der Divide-and-Conquer-Methode einen konsistenten und vorhersehbaren Sortierprozess bereitzustellen. Diese Strategie ermöglicht es Merge Sort, sowohl kleine als auch große Datensätze effektiv zu verarbeiten und garantiert in allen Fällen eine stabile Sortierung mit einer Zeitkomplexität von O(n log n).
Merge Sort verwendet den Teile-und-herrsche-Ansatz, der das Array in kleinere Unterarrays aufteilt, diese rekursiv sortiert und die sortierten Arrays dann wieder zusammenführt. Bei diesem Ansatz wird das Problem in überschaubare Abschnitte unterteilt, wobei jeder Abschnitt einzeln sortiert und effizient kombiniert wird. Dadurch ist der Algorithmus auch bei großen Datenmengen gut leistungsfähig, indem er den Sortieraufwand aufteilt.
Rekursion ist ein Prozess, bei dem sich eine Funktion selbst aufruft, um eine kleinere Version desselben Problems zu lösen. Das Problem wird so lange heruntergebrochen, bis ein Punkt erreicht ist, an dem das Problem einfach genug ist, um direkt gelöst zu werden. Dies wird als Basisfall bezeichnet.
Unten finden Sie eine Implementierung von Merge Sort in JavaScript, die zeigt, wie das Array rekursiv aufgeteilt und zusammengeführt wird:
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);
}
Nach dem Login kopieren
Um besser zu verstehen, wie Merge Sort funktioniert, gehen wir den Prozess anhand des Arrays durch: [38, 27, 43, 3, 9, 82, 10]
Schritt 1: Rekursive Division (mergeSort-Funktion)
Das Array wird rekursiv in kleinere Unterarrays aufgeteilt, bis jedes Unterarray nur noch ein Element enthält. Dies geschieht durch die folgenden Zeilen in der mergeSort-Funktion:
function mergeSort(arr) {
if (arr.length <= 1) return arr;
Nach dem Login kopieren
Das stoppt unsere Rekursion.
So verläuft die rekursive Aufteilung:
-
Erster Aufruf: mergeSort([38, 27, 43, 3, 9, 82, 10])
- Das Array wird in der Mitte geteilt:
[38, 27, 43] und [3, 9, 82, 10]
-
Erste Hälfte:
-
mergeSort([38, 27, 43])
- In der Mitte aufgeteilt: [38] und [27, 43]
-
mergeSort([27, 43])
- Aufgeteilt in [27] und [43]
- Die Unterarrays [38], [27] und [43] sind jetzt einzelne Elemente und können zusammengeführt werden.
-
Zweite Hälfte:
-
mergeSort([3, 9, 82, 10])
- Aufteilung in der Mitte: [3, 9] und [82, 10]
-
mergeSort([3, 9])
- Aufgeteilt in [3] und [9]
-
mergeSort([82, 10])
- Aufgeteilt in [82] und [10]
- Die Unterarrays [3], [9], [82] und [10] können jetzt zusammengeführt werden.
Schritt 2: Zusammenführen der sortierten Subarrays (Merge-Funktion)
Jetzt beginnen wir mit der Zusammenführung der Subarrays in sortierter Reihenfolge mithilfe der Zusammenführungsfunktion:
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);
}
Nach dem Login kopieren
So funktioniert der Zusammenführungsprozess:
Erste Zusammenführung (aus den Basisfällen):
- [27] und [43] zusammenführen → Ergebnis ist [27, 43]
- [38] mit [27, 43] zusammenführen → Ergebnis ist [27, 38, 43]
An diesem Punkt ist die linke Hälfte des Arrays vollständig zusammengeführt: [27, 38, 43].
Zweite Zusammenführung (aus den Basisfällen):
- [3] und [9] zusammenführen → Ergebnis ist [3, 9]
- [82] und [10] zusammenführen → Ergebnis ist [10, 82]
- Füge [3, 9] mit [10, 82] zusammen → Ergebnis ist [3, 9, 10, 82]
Jetzt ist die rechte Hälfte vollständig zusammengeführt: [3, 9, 10, 82].
Schritt 3: Endgültige Zusammenführung
Abschließend werden die beiden Hälften [27, 38, 43] und [3, 9, 10, 82] mit der Merge-Funktion zusammengeführt:
Vergleichen Sie 27 (links[0]) und 3 (rechts[0]). Seit 3 < 27, addiere 3 zum Ergebnis.
Vergleichen Sie 27 und 9. Addieren Sie 9 zum Ergebnis.
Vergleichen Sie 27 und 10. Addieren Sie 10 zum Ergebnis.
Vergleichen Sie 27 und 82. Addieren Sie 27 zum Ergebnis.
Vergleichen Sie 38 und 82. Addieren Sie 38 zum Ergebnis.
Vergleichen Sie 43 und 82. Addieren Sie 43 zum Ergebnis.
Fügen Sie das verbleibende Element 82 aus dem rechten Array hinzu.
Das vollständig zusammengeführte und sortierte Array ist:
[3, 9, 10, 27, 38, 43, 82].
Zeitkomplexität: Bester, durchschnittlicher und schlechtester Fall: O(n log n)
Schauen wir es uns genauer an:
Teilen (O(log n)): Jedes Mal, wenn das Array in zwei Hälften geteilt wird, verringert sich die Größe des Problems. Da das Array bei jedem Schritt in zwei Hälften geteilt wird, ist die Häufigkeit, mit der Sie dies tun können, proportional zu log n. Wenn Sie beispielsweise 8 Elemente haben, können Sie diese dreimal halbieren (da log₂(8) = 3).
Zusammenführen (O(n)): Nach dem Teilen des Arrays führt der Algorithmus die kleineren Arrays der Reihe nach wieder zusammen. Das Zusammenführen zweier sortierter Arrays der Größe n dauert O(n) Zeit, da Sie jedes Element einmal vergleichen und kombinieren müssen.
全体の複雑さ (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) 時間の計算量と汎用性により、メモリに制約のある環境や、等しいキーを持つ要素の順序を維持するのに非常に貴重です。最新のプログラミング ライブラリにおけるその役割により、現実世界のアプリケーションでも関連性が保たれます。
出典:
- Knuth、Donald E. The Art of Computer Programming、Vol. 3: 並べ替えと検索。アディソン・ウェスリー・プロフェッショナル、1997 年、158-160 ページ。
- コーメン、トーマス H.、他。アルゴリズムの紹介。 MIT Press、2009 年、第 2 章 (マージ ソート)、第 5 章 (アルゴリズムの複雑さ)、第 7 章 (クイックソート)。
- Silberschatz、Abraham、他。データベース システムの概念。 McGraw-Hill、2010 年、第 13 章 (外部並べ替え)。
- 「ティムソート。」 Python ドキュメント、Python ソフトウェア財団。
Python のティムソート
- 「Java 配列.sort」オラクルのドキュメント。
Java の Arrays.sort()
Das obige ist der detaillierte Inhalt vonMerge Sort Demystified: Ein Anfängerleitfaden zum Divide-and-Conquer-Sortieren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
