Ist zwar schon ein uraltes Topic aber: Der Algorithmus wird in der Praxis nicht mit 1-bit gerechnet sondern 8 oder 16. Es gibt i.d.R. nur sehr wenige Iterationen. Der Algorithmus ist nicht universell einsetzbar sondern nur für ganz bestimmte Fälle geeignet, daher ist ein Vergleich mit anderen Verfahren problematisch...

Algorithmus ist vor allem gedacht, um ganze Zahlen in einem bestimmten, im Voraus bekannten Intervall zu sortieren. Der Algorithmus vergleicht nie zwei Zahlen miteinander. Er arbeitet zwar out-of place, dafür aber stabil und O(n).

delfiphan hat folgendes geschrieben :

Ist zwar schon ein uraltes Topic aber: Der Algorithmus wird in der Praxis nicht mit 1-bit gerechnet sondern 8 oder 16. Es gibt i.d.R. nur sehr wenige Iterationen. Der Algorithmus ist nicht universell einsetzbar sondern nur für ganz bestimmte Fälle geeignet, daher ist ein Vergleich mit anderen Verfahren problematisch... Algorithmus ist vor allem gedacht, um ganze Zahlen in einem bestimmten, im Voraus bekannten Intervall zu sortieren. Der Algorithmus vergleicht nie zwei Zahlen miteinander. Er arbeitet zwar out-of place, dafür aber stabil und O(n).

Sicher kann man die Anzahl der Schleifen reduzieren, indem man statt bitweise zu sortieren das z.B. bytweise vollführt, jedoch kommt dann sofort die größere Anzahl "Eimer" bzw. "Buckets" als (nicht unbedingt nachteilige) Bedingung hinzu - bei Bytes sind auch nur 256, bei word immerhin schon 65536. Im Extremfall hat man für jede integre Zahl einen Eimer bzw. Bucket und sich voll von diesem (speziellen) Sortierverfahren verabschiedet, sondern ist wieder beim gewöhnlichen Bucketsort: Distribution Counting.

Ja, und letztlich können nur integre Zahlen (?) mit solchen speziellen Sortieralgorithmen sortiert werden, konkrete Sortierelemente, die oft genug aus komplexeren Datenstrukturen (records o.ä.) bestehen und bei denen nur ein Teil ("Schlüssel") für die Vergleichsoperationen herhalten muß, können nicht bedient (also verglichen und ggf. sortiert) werden - für die Praxis damit weitgehend untauglich. Deshalb teile ich diese Begeisterung, die in dieser Diskussion eingangs gezeigt wurde, auch in keiner Weise.

alzaimar hat folgendes geschrieben :

Dein Sortierkino lässt leider keinen echten Performancevergleich zu: Hier sind die AVL- und B-Sortierungen auch visuell schneller, weil die 'Bremse' nur beim Zeichnen der Linien greift, nicht jedoch bei den Vorbereitungen (Schreiben in die Datenstruktur).

Das ist m.E. kein Argument. Die Bremse soll nämlich gar nicht (primär) die Sortieralgorithmen verlangsamen, sondern lediglich die Darstellung derselben. Da solche relativ komplizierten Datenstrukturen wie AVL- und B-Bäume entsprechend anspruchsvolle Algorithmen erfordern, die sich leider nicht im Detail visualisieren lassen (jedenfalls nicht, indem man einfach die Sortiermenge mit ihren Veränderungen "öffentlich" darstellt), ist die Bremse bei diesen Sortierungen leider nicht mit einem echten Informationszuwachs verknüpft. Ohne Bremse - damit lassen sich die Algorithmen noch am ehesten vergleichen - sind von den von mir implementierten Algorithmen AVL- und B-Sort (mit Ausnahme der speziellen Sortierungen) eindeutig am schnellsten. Für substantiierte Geschwindigkeitsmessungen und -vergleiche ist mein Programm weder gedacht noch geeignet (es soll vielmehr die Augen verwöhnen). Aber mein Interesse für Deine Ideen ist geweckt - ich melde mich am anderen Orte wieder.