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

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