W
hustbaer schrieb:
wxSkip schrieb:
EDIT:
hustbaer schrieb:
Wikipedia schrieb:
Introsort or introspective sort is a sorting algorithm designed by David Musser in 1997. It begins with quicksort and switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted.
D.h. so lange Introsort nicht umschaltet *ist* es ein Quicksort. Der minimale Overhead die Rekursionstiefe mitzuzählen fällt dabei wirklich nicht ins Gewicht.
Jetzt klar?
Hey, genau so habe ich das auch "erfunden", inklusive logarithmischer Berechnung . Und dort liegt eben auch der Unterschied in der Geschwindigkeit von Introsort.
Bist du sicher?
Bei den allermeisten Inputs schaltet std::sort nämlich nicht um.
Könnte auch daran liegen wie du das Pivot Element ermittelt hast (üblich ist "Median of 3 Medians of 3"), bzw. wann du für kleine Mengen auf Insertion-Sort umgeschaltet hast.
Aha, doch falsch verstanden
Am Pivotelement liegt es nicht, beim Durchschnitt aus 2 oder 3 Elementen ist es bei mir ziemlich genau gleich schnell.
@SortierFachmann: Dann erklär mir doch mal, was dich daran hindert, nachdem Thread 1 mit der 10-Elemente-Liste fertig ist, die zwei Teile aus der 100000-Elemente-Liste wieder auf 2 Threads aufzuteilen? Ich glaube nicht, dass der Zeitraum, der benötigt wird, um einen Thread zu erstellen, so groß ist, dass Mergesort da schneller wird.