Quicksort mit zwei Pivots und mehr: Eine mathematische Analyse von Mehrwege-Partitionierungsverfahren und der Frage, wie Quicksort dadurch schneller wird

Abstract

Seit 2011 kommt in der Java runtime library eine Quicksort-Variante mit zwei Pivots zum Einsatz, von der lange unklar war, warum sie gegenüber der vorherigen, ausoptimierten Quicksort-Implementierung nochmals über 10% Laufzeit einsparen kann. Das verwundert umso mehr, da frühere Untersuchungen keinen Vorteil in der Verwendung mehrerer Pivots erwarten ließen. Durch eine umfassende mathematische Analyse aller sinnvollen Quicksort-Varianten konnte ich beweisen, dass durch die Verwendung mehrerer Pivots tatsächlich keine wesentliche Ersparnis bei der Anzahl an Vergleichen, und allgemeiner dem Aufwand innerhalb der CPU, zu erwarten ist, wohl aber eine deutliche Reduktion des Datenvolumens, das zwischen Hauptspeicher und CPU transferiert werden muss. Diese effizientere Nutzung der Speicherhierarchie ist dabei nur durch den Einsatz mehrerer Pivots, und durch keine andere der vielen bekannten Optimierungen von Quicksort zu erreichen.