Der Algorithmus
Der MergeSort-Algorithmus ist ein stabiler Sortieralgorithmus nach dem Teile-und-Herrsche-Prinzip. Im ersten Teil wird das Array rekursiv so lange halbiert, bis in jeder Liste nur noch 1 Element vorhanden ist. Bei einer Liste mit einem Element geht man davon aus, dass die Liste automatisch als sortiert gilt. Danach können alle nachfolgenden Operationen von zwei sortierten Listen ausgehen, wodurch weniger Operationen beim Zusammenführen ausreichen um ein neues sortiertes Array zu erhalten.
Im zweiten Teil werden die bereits sortierten Listenhälften verglichen und mit der Komplexität O(n) je rekursiver Iteration verglichen und zusammengeführt (siehe den nachfolgenden JAVA Code).
package AlgoDat;
public class MergeSort {
// Zu sortierendes Array
private int myArray[] = {22, 6, 2, 4, 10, 3, 9, 7, 5, 8, 1};
// Hält die Klasse als instanziertes Objekt
@SuppressWarnings("unused")
private static MergeSort program;
// Hilfsfunktion für das Ausgeben des Arrays
public void OutputOfIntArray(int myArray[])
{
if (myArray != null)
{
for (int i = 0; i < myArray.length; i++) {
if (i > 0) System.out.print(";");
System.out.print(myArray[i]);
}
System.out.println();
}
}
public void mergeSort(int myArray[])
{
// zunächst wird das Array ab der Hälfte in zwei
// Arrays links und rechts geteilt, das passiert
// rekursiv ... und zwar so lange bis jedes Element
// für sich nur noch 1x vorhanden ist (Teile-Herrsche-Prinzip).
// Das Teilen ist damit erledigt und nun sollte da
// Problem dadurch beherrschbarer werden -> nun
// werden die Einzelelemente wieder in Arrays sortiert.
// Die Abbruchbedingung der Rekursion ist, wenn die Liste
// nur noch ein einziges Element hat, wobei die Liste bei
// einem einzigem Element als sortiert gilt.
if (myArray.length == 1) return;
// weist bei ungeraden Zahlen eine abgerundete Ganzzahl zu
int indexHaelfte = myArray.length / 2;
int[] linkeHaelfte = new int[indexHaelfte];
// Die abgerundete Ganzzahl kann von der Länge abgezogen werden
// um die Größe des rechten Arrays zu erhalten.
int[] rechteHaelfte = new int[myArray.length - indexHaelfte];
// Befülle die linke Hälfte
for (int i = 0; i < indexHaelfte; i++)
{
linkeHaelfte[i] = myArray[i];
}
// Befülle die rechte Hälfte
for (int i = indexHaelfte; i < myArray.length; i++)
{
rechteHaelfte[i - indexHaelfte] = myArray[i];
}
// Hier ist der rekursive Aufruf, indem die beiden Hälften an
// die mergeSort-Methode selbst übergeben wird.
this.mergeSort(linkeHaelfte);
this.mergeSort(rechteHaelfte);
// Hier werden die beiden Arrays wieder kombiniert (geMerged)
this.merge(myArray, linkeHaelfte, rechteHaelfte);
}
private void merge(int[] mergeArray, int[] linkeHaelfte, int[] rechteHaelfte)
{
System.out.print("Vergleiche linke Hälfte: ");
this.OutputOfIntArray(linkeHaelfte);
System.out.print("mit rechter Hälfte ");
this.OutputOfIntArray(rechteHaelfte);
int iteratorLinks = 0, iteratorRechts = 0, iteratorMergeArray = 0;
// Da die linke und reche Hälfte bereits sortiert sind, funktioniert die Zuweisung
// in ein neues Array mit einer einzigen Schleife der Komplexität/Ordnung O(n).
while (iteratorLinks < linkeHaelfte.length && iteratorRechts < rechteHaelfte.length)
{
if (linkeHaelfte[iteratorLinks] <= rechteHaelfte[iteratorRechts])
{
mergeArray[iteratorMergeArray] = linkeHaelfte[iteratorLinks];
iteratorLinks++;
}
else
{
mergeArray[iteratorMergeArray] = rechteHaelfte[iteratorRechts];
iteratorRechts++;
}
iteratorMergeArray++;
}
// Wenn noch Elemente in der linken Hälfte waren, die nicht verglichen wurden,
// werden diese dem Merged Array hinzugefügt
while (iteratorLinks < linkeHaelfte.length)
{
mergeArray[iteratorMergeArray] = linkeHaelfte[iteratorLinks];
iteratorLinks++;
iteratorMergeArray++;
}
// Wenn noch Elemente in der rechten Array-Hälfte waren, die nicht verglichen wurden,
// werden diese dem Merged Array hinzugefügt
while (iteratorRechts < rechteHaelfte.length)
{
mergeArray[iteratorMergeArray] = rechteHaelfte[iteratorRechts];
iteratorRechts++;
iteratorMergeArray++;
}
}
// Konstruktor
public MergeSort()
{
System.out.print("Vorher: ");
this.OutputOfIntArray(myArray);
// Wir lagern alles weitere in eine eigene Methode aus,
// da MergeSort ein rekursiver Algorithmus ist, dessen
// Funktion aufgerufen werden muss und beeginnen mit dem
// unsortierten Array
this.mergeSort(myArray);
System.out.print("Nachher: ");
this.OutputOfIntArray(myArray);
}
public static void main(String[] args)
{
// Instanziere aus den statischem Programm ein echtes Objekt
// damit nicht alle Methoden und Variablen static sein müssen.
program = new MergeSort();
}
}
Ausgabe
Vorher: 22;6;2;4;10;3;9;7;5;8;1
Vergleiche linke Hälfte: 22
mit rechter Hälfte 6
Vergleiche linke Hälfte: 4
mit rechter Hälfte 10
Vergleiche linke Hälfte: 2
mit rechter Hälfte 4;10
Vergleiche linke Hälfte: 6;22
mit rechter Hälfte 2;4;10
Vergleiche linke Hälfte: 9
mit rechter Hälfte 7
Vergleiche linke Hälfte: 3
mit rechter Hälfte 7;9
Vergleiche linke Hälfte: 8
mit rechter Hälfte 1
Vergleiche linke Hälfte: 5
mit rechter Hälfte 1;8
Vergleiche linke Hälfte: 3;7;9
mit rechter Hälfte 1;5;8
Vergleiche linke Hälfte: 2;4;6;10;22
mit rechter Hälfte 1;3;5;7;8;9
Nachher: 1;2;3;4;5;6;7;8;9;10;22
Komplexität: O-Notation (Ordnung)
Der MergeSort besteht aus 3 Teilen, die sich zu der Gesamtkomplexität zusammensetzen.
Teil 1: (Rekursives) Teilen
Wenn wir ein Array der Größe n in zwei Hälften teilen, benötigen wir
Schritte. Hierbei handelt es sich um den Logarithmus dualis, also den Logarithmus zur Basis 2 (wessen Basis für die 2 Hälften spricht, in die aufgeteilt wird). Dies liegt also daran, dass wir die Liste in jeder Rekursionsebene halbieren. Wir fragen hier also mit welcher Zahl man 2 potenzieren muss um n zu erhalten.
Wenn wir in dem unsortierten Array 11 Elemente haben, würden wir also fragen, mit welcher Zahl wir 2 potenzieren müssen um 11 zu erhalten. Den Exponenten den wir hier erhalten wäre 4:
Wir runden die Kommazahl immer auf die nächste volle Zahl auf, da wir keine halben Schritte machen können. Die Zahl 4 entspricht hier auch der Rekursionstiefe, die benötigt wird bis der aktuelle Rekursions-Heap nur noch aus einem Element bekommt, was zu Abbruch der Rekursion führt.
Der erste Teil besitzt somit die Ordnung:
Teil 2 und 3: Sortieren und Mergen
Der Schritt des Zusammenführens (des Mergens) beider Liste ist mit der Sortierung kombiniert. Hier wird vorausgesetzt dass bereits sortierte Listenhälften vorliegen, da man zwei bereits sortierte Arrays mit der Komplexität n vergleichen kann. Beim Zusammenführen der sortierten Teillisten benötigen wir
Zeit. Dieser Schritt ist linear abhängig von der Gesamtanzahl der Elemente.
Gesamt-Komplexität
Somit ergibt sich die Gesamtkomplexität:
im Worst-, Normal- und Best-Case.
