Wie gehts?
Blendend, nachdem ich bei der "Extraktion" des eigentlichen Algorithmus und Quellcodevereinfachung weit vorangeschritten bin.
Als Sortieralgorithmus dürfte sich das
imho nicht lohnen, denn beim Sortieren wird zwar oft verglichen, aber selten direkt gesucht. Aber ich lasse mich gerne eines Besseren belehren.
Lohnen? Für mein Sortieranimationsprogramm lohnt sich
jeder Algorithmus. Und wenn die Arbeitsweise dabei nicht offensichtlich wird, dann erlaubt das zumindest doch eine erste Abschätzung der Geschwindigkeit (wenn auch keine sichere "gefühlte" Zuordnung zur Komplexitätsklasse, s. z.B. Select(ion)sort (das läuft bei mir schnell, ist aber dennoch O(n^2)).
Splaysort benötigt, wie die anderen, auf dynamischen Speicherstrukturen beruhenden Algorithmen (in die eingeordnet und aus denen gelesen wird), reichlich zusätzlichen Speicher, ist also ex situ, allerdings von der Geschwindigkeit her O(n*log(n)). Erste "ungraphische" Ergebnisse scheinen das zu bestätigen.