Merge Sort ist ein effizienter Sortieralgorithmus, der auf Merge-Operationen basiert. Dieser Algorithmus ist eine sehr typische Anwendung des Divide-and-Conquer-Ansatzes.

Betrachten wir zunächst, wie man zwei geordnete Sequenzen zusammenführt. Das ist ganz einfach: Man vergleicht die ersten Zahlen der beiden Sequenzen, nimmt zuerst die kleinere und löscht diese Zahl nach dem Entnehmen aus der entsprechenden Sequenz. Dann vergleicht man erneut; wenn eine Sequenz leer ist, entnimmt man einfach die Daten der anderen Sequenz nacheinander.

// Geordnete Arrays a[] und b[] in c[] zusammenführen void MemeryArray(int a[], int n, int b[], int m, int c[]) { int i, j, k; i = j = k = 0; while (i < n && j < m) { if (a[i] < b[j]) c[k++] = a[i++]; else c[k++] = b[j++]; } while (i < n) c[k++] = a[i++]; while (j < m) c[k++] = b[j++]; }

Es ist ersichtlich, dass das Zusammenführen geordneter Sequenzen relativ effizient ist und O(n) erreichen kann.

Nachdem wir das obige Problem des Zusammenführens geordneter Sequenzen gelöst haben, betrachten wir nun Merge Sort. Die Grundidee besteht darin, das Array in zwei Gruppen A und B aufzuteilen. Wenn die Daten innerhalb jeder Gruppe geordnet sind, können diese beiden Datengruppen bequem sortiert werden. Wie können die Daten innerhalb dieser beiden Gruppen geordnet werden?

Sie können die Gruppen A und B weiter in jeweils zwei Gruppen unterteilen. Und so weiter. Wenn eine unterteilte Untergruppe nur ein Datenelement enthält, kann die Untergruppe als bereits sortiert betrachtet werden, und dann werden die beiden benachbarten Untergruppen zusammengeführt. Auf diese Weise wird die Mischsortierung abgeschlossen, indem die Sequenz zuerst rekursiv zerlegt und dann die Sequenzen zusammengeführt werden.

// Zwei sortierte Folgen a[first...mid] und a[mid...last] zusammenführen. void mergearray(int a[], int first, int mid, int last, int temp[]) { int i = first, j = mid + 1; int m = mid, n = last; int k = 0; while (i <= m && j <= n) { if (a[i] <= a[j]) temp[k++] = a[i++]; else temp[k++] = a[j++]; } while (i <= m) temp[k++] = a[i++]; while (j <= n) temp[k++] = a[j++]; for (i = 0; i < k; i++) a[first + i] = temp[i]; } void mergesort(int a[], int first, int last, int temp[]) { if (first < last) { int mid = (first + last) / 2; mergesort(a, first, mid, temp); // Linke Seite ist sortiert mergesort(a, mid + 1, last, temp); // Rechte Seite ist sortiert mergearray(a, first, mid, last, temp); // Dann die beiden sortierten Folgen zusammenführen } } bool MergeSort(int a[], int n) { int *p = new int[n]; if (p == NULL) return false; mergesort(a, 0, n - 1, p); delete[] p; return true; }

Die Effizienz von Mergesort ist relativ hoch. Die Länge der Folge sei N. Insgesamt sind logN Schritte erforderlich, um die Folge in kleine Folgen zu unterteilen. Jeder Schritt ist ein Prozess des Zusammenführens sortierter Folgen, und die Zeitkomplexität kann als O(N) angegeben werden, sodass sich insgesamt O(N*logN) ergibt. Da Mergesort jedes Mal mit benachbarten Daten arbeitet, ist Mergesort unter mehreren Sortierverfahren mit O(N*logN) (Quicksort, Mergesort, Shellsort, Heapsort) ebenfalls relativ effizient.

Auf meinem Computer habe ich Bubblesort, direkte Einfügesortierung, Mergesort und die direkte Verwendung des systemeigenen qsort() verglichen (alles in der Release-Version).

Test mit 20,000 zufälligen Datenelementen:

Test mit 50,000 zufälligen Datenelementen:

Test mit 200,000 zufälligen Datenelementen:

Hinweis: Einige Bücher reservieren in mergearray() beim Zusammenführen geordneter Sequenzen ein temporäres Array, aber zu viele new-Operationen sind sehr zeitaufwändig. Daher wurde eine kleine Änderung vorgenommen. In MergeSort() wird nur ein temporäres Array mit new reserviert. Alle nachfolgenden Operationen teilen sich dieses temporäre Array.

Autor: MoreWindows

Original: https://blog.csdn.net/morewindows/article/details/6678165