13.1 Mergesort

Einfacher Mergesort

Bevor wir den "richtigen", also den rekursiven Mergesort behandeln, wollen wir einmal den "einfachen" Mergesort kennenlernen, also ein Sortierverahren, dass zwar im Prinzip so arbeitet wie der Mergesort, aber viel einfacher zu verstehen und zu implementieren ist.

Betrachten wie folgende Abbildung:

Das Grundprinzip des einfachen Mergesorts

In der Reihe A haben wir 22 ungeordnete ganze Zahlen im Bereich 1..250.

In der Reihe B wurden die Zahlen in zwei gleich große Hälften unterteilt.

In der Reihe C wurde jede Hälfte für sich sortiert.

In der Reihe D wurden die beiden Hälften wieder zusammengeführt.

Zeitverhalten

Überlegen wir einmal. Angenommen, wir würden jede Hälfte des Arrays mit Hilfe eines Bubblesorts sortieren. Bei 11 Zahlen würden wir dann ca. 11² = 121 Zeiteinheiten benötigen. Bekanntlich kann das Zeitverhalten der einfachen Sortierverfahren ja mit O(N) = N² beschrieben werden.

Natürlich haben wir es mit zwei Hälften zu tun, damit würde sich also die Sortierzeit verdoppeln. Aber eine Verdopplung der Sortierzeit spielt bei der O-Notation ja keine Rolle. Das Zeitverhalten wäre immer noch O(N) = N², allerdings würden wir jetzt 242 Zeiteinheiten benötigen.

Dazu kommt noch die Zeit, die für den Merge-Vorgang benötigt wird, also für das Zusammenfügen der beiden sortierten Arrays. Hier wird immer eine Zahl aus der einen Hälfte mit einer anderen Zahl als der zweiten Hälfte verglichen. Das wären noch einmal 11 Vergleiche bzw. 11 Zeiteinheiten, also kommen wir insgesamt auf ca. 250 Zeiteinheiten (wir wollen ja nicht kleinlich sein).

Hätten wir jetzt alle 22 Zahlen nach dem Bubblesort-Verfahren sortiert, würde man 22² = 484 Zeiteinheiten benötigen.

Fazit: Dieser einfache Mergesort hat zwar das gleiche Zeitverhalten O(N) = N² wie der Bubblesort, ist aber im Schnitt doppelt so schnell.

Bevor wir auf den richtigen Mergesort zu sprechen kommen, wollen wir uns eine Implementation dieses einfachen Mergesorts ansehen.

import java.util.Random;

public class Zahlen
{
    final int max = 200;

    public Zahlen()
    {
        int[] ganzerArray = erzeugen();

        int[] links  = sortieren(gibLinkeHaelfe(ganzerArray));
        int[] rechts = sortieren(gibRechteHaelfe(ganzerArray));      
        
        System.out.println("Die linke Haelfte des Arrays, sortiert: ");
        anzeigen(links);
        System.out.println("Die rechte Haelfte des Arrays, sortiert: ");
        anzeigen(rechts);

        System.out.println("Beide Haelften werden jetzt vereinigt: ");
        ganzerArray = verschmelze(links, rechts);
        anzeigen(sortieren(ganzerArray));        
    }

    public int[] erzeugen()
    {
        int[] liste = new int[max];
        Random zufall = new Random();       

        for (int i = 0; i < max; i++)
            liste[i] = zufall.nextInt(9999)+1;
        return liste;
    }

    public int[] gibLinkeHaelfe(int[] pArray)
    {
        int max2 = max/2;
        int[] links = new int[max2];

        for (int i=0; i < max2; i++)
            links[i] = pArray[i];     

        return links;
    }

    public int[] gibRechteHaelfe(int[] pArray)
    {
        int max2 = max/2;
        int[] rechts = new int[max2];

        for (int i=0; i < max2; i++)
            rechts[i] = pArray[max2+i];     

        return rechts;
    }    

    public int[] sortieren(int[] pArray)
    {
        int temp;

        for (int durchgang = 1; durchgang < pArray.length; durchgang++)
            for (int i=0; i < pArray.length-1; i++)
                if (pArray[i] > pArray[i+1])
                {
                    temp = pArray[i]; 
                    pArray[i] = pArray[i+1];
                    pArray[i+1] = temp;
                }
        return pArray;
    }

    public int[] verschmelze(int[] lArray, int[] rArray)
    {
        int[] ergebnis = new int[max];
        int pl = 0;
        int pr = 0;
        
        for (int i=0; i < max; i++)
           if ((pl > max/2-1) && (pr < max/2))      // ist links schon fertig?
              ergebnis[i] = rArray[pr++];
           else if ((pr > max/2-1) && (pl < max/2)) // ist rechts schon fertig?
              ergebnis[i] = lArray[pl++];
           else if (lArray[pl] < rArray[pr])        // Element aus linken Array einfuegen
              ergebnis[i] = lArray[pl++];
           else                                     // Element aus rechtem Array einfuegen 
              ergebnis[i] = rArray[pr++];
        
        return ergebnis;
    }

    public void anzeigen(int[] pArray)
    {
        for (int i = 1; i<=pArray.length; i++)   
        {
            System.out.print(pArray[i-1] + "\t");
            if (i % 10 == 0)
                System.out.println();
        }
    }
}

Dieses Java-Programm ist übrigens auf "meinem eigenen Mist gewachsen", wie man so sagt und nicht mit den Mergesort-Programmen vergleichbar, die man im Internet findet. Das Programm soll lediglich das Grundprinzip des Mergesort illustrieren.

erzeugen()

In dieser Methode wird ein Array mit Zufallszahlen erzeugt und zurückgegeben. Das Programm arbeitet also nicht wie sonst bei mir üblich mit einem Array-Attribut, auf das alle Methoden Zugriff haben, sondern die Arrays werden als Parameter übergeben.

gibLinkeHaelfte()

Diese Methode nimmt einen int-Array als Parameter an und liefert die linke Hälfte dieses Arrays zurück.

gibRechteHaelfte()

Diese Methode nimmt einen int-Array als Parameter an und liefert die rechte Hälfte dieses Arrays zurück.

Natürlich hätte man dieses Aufteilen des Arrays in zwei Hälften einfacher machen können. Die meisten Algorithmen, die man im Internet findet, benutzen dazu die drei Variablen L, M und R für die Indices des linken, des mittleren und des rechten Elementes. Aber ich wollte den Quelltext hier möglichst einfach halten, so dass alle Schüler(innen) meiner Informatikkurse ihn auch verstehen.

sortieren()

Diese Methode arbeitet nach dem Bubblesort-Algorithmus. Der als Parameter übergebene Array wird sortiert und dann zurück gegeben.

anzeigen()

Damit wird der als Parameter übergebene Array in der Konsole angezeigt.

verschmelzen()

Das ist die aufwendigste Methode überhaupt. Ich erkläre sie mal an dem Beispiel aus Abbildung 1.

Der zentrale Vergleich

Zwei Hilfszeiger pl und pr werden am Anfang auf 0 gesetzt. Sie zeigen auf das erste Element des linken bzw. rechten Teil-Arrays. Der neue Gesamtarray ergebnis wird initialisiert, der Zeiger i auf ergebnis wird auch auf 0 gesetzt.

Nun wird geschaut, welches der beiden Elemente lArray[0] oder rArray[0] kleiner ist. Das jeweils kleinere Element wird dann in den neuen Gesamtarry an Position 0 geschrieben. In diesem konkreten Fall ist das erste Element von lArray (21) kleiner als das erste Element von rArray (50), also wird die 21 an die erste Position des Gesamtarrys geschrieben. Die Hilfszeiger i und pl können damit inkrementiert werden, der Hilfszeiger pr bleibt zunächst auf der 50 stehen, wird also nicht inkrementiert.

Im zweiten Durchgang werden die 34 und die 50 verglichen, im dritten Durchgang die 45 und die 50. Nach dem dritten Durchgang sieht die Situation folgendermaßen aus:

Die Situation nach dem 3. Durchgang

Im vierten Durchgang (i = 3) gilt die Bedingung

lArray[pl] < rArray[pr]

nicht mehr. Daher wird jetzt die 50 an die vierte Stelle (i = 3) des Gesamtarray geschrieben.

Im fünften Durchgang (i = 4) wird die 66, im sechsten Durchgang (i = 5) die 77, im siebten Durchgang (i = 6) die 93 und im achten Durchgang (i = 7) die 100 in den Gesamtarray geschrieben. Der Zeiger pl hat jetzt immer noch den Wert 3, während pr den Wert 4 hat.

So geht das immer weiter, bis einer der beiden Zeiger das Ende seines Arrays erreicht hat. Ist einer der beiden Arrays "fertig" abgearbeitet worden, dann können die restlichen Zahlen des anderen Arrays einfach in den Hauptarry kopiert werden. Um diese Endbedingung "kümmern" sich die beiden ersten if-else-Bedingungen des Quelltextes.