Teile und herrsche

Teile und herrsche ist ein Konzept, um Algorithmen zu entwickeln. Es beschreibt die Vorgehensweise, ein algorithmisches Problem in kleinere Teilprobleme aufzuteilen und diese einzeln zu lösen.

Nachdem ein kleineres Teilproblem gelöst wurde, lassen sich meist Aussagen über diese kleinere Lösung treffen. Mit deren Hilfe kann das Gesamtproblem leichter gelöst werden.

Einige Sortierverfahren funktionieren nach diesem Konzept: Anstatt eine gegebene Menge vollständig zu sortieren, werden zuerst einzelne Teile der Menge sortiert. Wenn die kleineren Teilmengen sortiert sind, lassen sie sich einfacher ineinander verschachteln, um eine größere, sortierte Gesamtmenge zu erhalten.