Vor ein paar Jahren gab es in der c't einen Artikel. Der Titel hieß entweder "QuickerSort" oder er enthielt zumindest diesen Begriff. Der Clou in diesem Artikel war, Quicksort mit Bubblesort zu kombinieren, da beide Algorithmen unter unterschiedlichen Voraussetzungen degenerieren, sich also deshalb gegenseitig den Worst-Case vom Hals halten. Dabei wird im Prinzip der Quicksort-Algorithmus verwendet. Beim Scannen einer Teil-Liste, werden aber auch benachbarte Werte miteinander verglichen. Werden dabei Werte gefunden, die in der falschen Reihenfolge sortiert sind, dann werden auch diese getauscht (Bubblesort), Werden dagegen keine Unregelmäßigkeiten gefunden, dann ist klar, dass zumindest diese Teilliste bereits sortiert ist, und es findet keine Rekursion innerhalb dieser Teilliste mehr statt. Bei Listen, die bereits sortiert vorliegen, bricht der Algorithmus ohne Rekursion ab, ist also erheblich schneller, als QuickSort. Bei unsortierten Listen ist der Algorithmus geringfügig langsamer, als Quicksort. Auch unter ungünstigen Umständen, nimmt die Geschwindigkeit aber nicht so stark ab, wie bei Quicksort. Mein erkauft sich also eine wesentlich größere Robustheit mit einem geringfügigen Performance-Verlust Ich kann hier nicht allzuviel zur Theorie beisteuern, denke aber, dass dies eine interessante Erweiterung des Artikels darstellt. Kann jemand etwas daraus machen? Gruß, Matthias - Ich denke, das ist durch den Absatz Varianten und dem weiterführenden Artikel Introsort abgedeckt. -- Nalpak01 22:12, 25. Okt. 2006 (CEST)