Merge Sort

Merge Sort ist das Musterbeispiel für Teile und herrsche: Ein großes Problem wird so lange halbiert, bis die Teile trivial sind, und die Lösungen werden anschließend wieder zusammengesetzt.

Der Algorithmus ist vorhersehbar schnell. Er braucht immer O(n log n) Schritte, auch im schlechtesten Fall. Dafür benötigt er zusätzlichen Speicher, weil beim Zusammenfügen ein neues Array entsteht.

Der Ablauf besteht aus zwei Hälften.

Teilen. Das Array wird in der Mitte geteilt, und beide Hälften werden auf genau dieselbe Weise sortiert. Diese Rekursion endet, sobald ein Teil nur noch aus einem einzigen Element besteht, denn das ist per Definition sortiert.

Zusammenfügen. Zwei bereits sortierte Hälften lassen sich sehr einfach mischen: Man schaut nur auf das jeweils vorderste Element beider Hälften, nimmt das kleinere und rückt dort eine Position weiter. Jedes Element wird dabei genau einmal angefasst.

Das Halbieren erzeugt log n Ebenen, und auf jeder Ebene wird jedes Element einmal kopiert. Daraus ergeben sich die n · log n Schritte.

public static class MergeSort
{
    // Liefert ein neues sortiertes Array und lässt die Eingabe unverändert.
    public static int[] Sort(int[] numbers)
    {
        // Ein Array mit null oder einem Element ist per Definition sortiert - das beendet die Rekursion.
        if (numbers.Length <= 1)
            return numbers;

        var middle = numbers.Length / 2;

        // In der Mitte teilen und beide Hälften auf genau dieselbe Weise sortieren.
        var left = Sort(numbers[..middle]);
        var right = Sort(numbers[middle..]);

        return Merge(left, right);
    }

    // Läuft durch beide sortierten Hälften zugleich und nimmt immer das kleinere vordere Element.
    private static int[] Merge(int[] left, int[] right)
    {
        var merged = new int[left.Length + right.Length];
        var leftIndex = 0;
        var rightIndex = 0;

        for (var i = 0; i < merged.Length; i++)
        {
            var takeFromLeft = rightIndex >= right.Length
                || (leftIndex < left.Length && left[leftIndex] <= right[rightIndex]);

            merged[i] = takeFromLeft ? left[leftIndex++] : right[rightIndex++];
        }

        return merged;
    }
}

var numbers = new[] { 38, 27, 43, 3, 9, 82, 10 };

var sorted = MergeSort.Sort(numbers);

Console.WriteLine(string.Join(", ", sorted));

// Das Eingabe-Array bleibt unverändert.
Console.WriteLine(string.Join(", ", numbers));

3, 9, 10, 27, 38, 43, 82
38, 27, 43, 3, 9, 82, 10

• Merge Sort ist stabil, solange beim Gleichstand das Element aus der linken Hälfte zuerst genommen wird. Genau dafür steht das <= im Vergleich.
• Weil er die Daten sequenziell liest, eignet er sich auch für Datenmengen, die nicht in den Arbeitsspeicher passen.
• Die Variante hier gibt ein neues Array zurück und lässt die Eingabe unangetastet. Das ist gut lesbar, kostet aber Speicher.