Einige Strategien, um Algorithmen zu entwerfen, treten immer wieder auf, weil sie so erfolgreich sind - so zum Beispiel auch die Divide-and-Conquer-Strategie.
Divide and conquer – teile und herrsche
Oft kannst du ein Problem schneller lösen, indem du es zunächst in zwei kleinere Teilprobleme zerlegst (divide). Dann löst du die Teilprobleme (conquer), und aus diesen Lösungen setzt du die Gesamtlösung zusammen (combine).
Sortieren mit divide and conquer
Stell dir vor, du willst zusammen mit einem Freund einen Stapel von 32 Spielkarten sortieren:
Ihr teilt euch den Kartenstapel in zwei Hälften auf (divide),
dann sortiert jeder seinen Teilstapel für sich (conquer),
anschließend legt immer derjenige, der die kleinste Karte hat, diese auf einen neuen Stapel (combine).
Dann ist dieser Stapel am Ende sortiert.
Das Verrückte ist: Selbst wenn dein Freund dir nicht hilft, sondern wenn du alles alleine machst und dabei die Arbeit deines Freundes übernimmst, geht das Sortieren auf diese Art und Weise schneller.
Divide-and-conquer-Prinzip anwenden: Mergesort
Am schnellsten geht es, wenn du auch die Teilstapel wieder nach derselben Methode sortierst: Du teilst den Teilstapel in zwei Hälften auf, sortierst die Hälften jeweils für sich und führst sie anschließend zu einem sortierten Stapel zusammen.
Und so weiter. Solange ein Teilstapel aus mehr als einer Karte besteht, machst du immer so weiter.
Dies ist das Prinzip des Sortierverfahrens Mergesort. Der Name Mergesort nimmt Bezug auf das Zusammenführen oder Verschmelzen (engl.: to merge) der zwei sortierten Hälften.
Mergesort ist das Paradebeispiel eines Divide-and-Conquer-Algorithmus. Es gibt aber noch viele andere Beispiele, so etwa das Sortierverfahren Quicksort.
Schau dir am besten zuerst einmal das Sortierverfahren Mergesort an.
