bsort: A theoretically efficient non-comparison-based sorting algorithm for integer and floating-point numbers

Die Arbeit stellt bsort vor, einen theoretisch effizienten, nicht-vergleichsbasierten Sortieralgorithmus für Ganzzahlen und Gleitkommazahlen, der durch eine von Binärschnellsortieren abgeleitete Methode eine Laufzeit von $O(wn)$ und einen zusätzlichen Speicherbedarf von $O(w)$ erreicht.

Das Wesentliche

🎩 Der Zaubertrick zum Ordnen: Was ist bsort?

Stellen Sie sich vor, Sie haben einen riesigen Haufen durcheinander gewürfelter Spielkarten. Normalerweise sortiert man diese, indem man zwei Karten nebeneinander hält und vergleicht: „Ist die 7 kleiner als die 10? Ja? Dann kommt die 7 zuerst." Das ist wie bei den klassischen Sortieralgorithmen (wie Introsort in C++), die wir alle kennen. Sie vergleichen immer Paare. Das funktioniert gut, aber es braucht Zeit, besonders wenn die Zahlenhaufen riesig sind.

Der Autor dieses Papers, Benjamin Guzmán, hat einen anderen Weg gefunden: bsort.

Statt zu vergleichen, schaut bsort nicht auf den Wert der Zahl, sondern direkt auf ihre Binärcode-Struktur (die Nullen und Einsen, aus denen der Computer denkt). Man könnte sagen: Statt zu fragen „Ist A größer als B?", fragt bsort: „Hat A an dieser Stelle eine 1 oder eine 0?"

🏗️ Wie funktioniert das? (Die Analogie der Schachteln)

Stellen Sie sich vor, Sie haben einen großen Raum voller Menschen, die nach Größe sortiert werden sollen.

1. Der klassische Weg (Vergleichen): Jeder muss mit jedem reden. „Bist du größer als ich?" Das dauert lange.
2. Der bsort-Weg (Bitweise Trennung):
   • Schritt 1: Der Moderator ruft: „Alle, die eine gerade Schuhgröße haben, gehen links! Alle mit ungerader Schuhgröße gehen rechts!" (Das ist der erste Bit-Check).
   • Schritt 2: In der linken Gruppe ruft er: „Alle, deren zweite Ziffer der Schuhgröße eine 0 ist, bleiben links, die mit 1 gehen rechts."
   • Schritt 3: Das wiederholt sich immer weiter, Bit für Bit, bis jeder in seiner eigenen kleinen Gruppe steht.

Da Computer Zahlen als lange Reihen von Nullen und Einsen speichern, kann bsort diesen Prozess extrem schnell durchlaufen. Es sortiert nicht durch Vergleichen, sondern durch Aussortieren in zwei Gruppen (links/rechts) basierend auf einem einzigen Bit.

🧊 Das große Problem: Negative Zahlen und Kommazahlen

Das Problem bei diesem „Bit-Trick" ist, dass er für einfache positive Zahlen (wie 1, 2, 3) super funktioniert, aber bei negativen Zahlen (-1, -2) und Kommazahlen (3,14) ins Straucheln gerät.

• Das Negative-Problem: Im Computer werden negative Zahlen so gespeichert, dass die erste Ziffer (das Vorzeichen-Bit) eine 1 ist, während positive Zahlen eine 0 haben. Wenn man einfach nach 0 und 1 trennt, landen alle negativen Zahlen plötzlich nach den positiven Zahlen – genau falsch herum!

  • Die Lösung von bsort: Der Algorithmus merkt sich das. Beim ersten Schritt (dem Vorzeichen-Bit) dreht er die Richtung einfach um. Er sagt: „Okay, die 1er (Negativen) kommen jetzt links, die 0er (Positiven) rechts." So wird die Reihenfolge korrigiert, bevor es weitergeht.

• Das Kommazahl-Problem: Kommazahlen (wie 3,14) sind im Computer wie eine kleine Rechnung aufgebaut: Vorzeichen + Exponent (wie viele Nullen) + Mantisse (die eigentlichen Ziffern).

  • Die Lösung von bsort: Es sortiert diese in drei Runden:
    1. Erst nach dem Vorzeichen (Minus oder Plus).
    2. Dann nach dem Exponenten (wie groß ist die Zahl grob?).
    3. Und erst ganz zum Schluss nach den feinen Details (der Mantisse).
       Das ist wie wenn man eine Bibliothek erst nach Sprache sortiert, dann nach Buchgröße und erst am Ende nach dem Titel.

🏎️ Theorie vs. Praxis: Der schnelle Sportwagen mit einem Problem

Der Autor zeigt in seiner Arbeit zwei Seiten:

1. Die Theorie (Der Traum):
   Mathematisch gesehen ist bsort ein Wunder. Es ist extrem schnell, besonders wenn die Zahlen klein sind (wie bei 8-Bit-Zahlen, also Zahlen von 0 bis 255). Es braucht weniger Speicherplatz als andere Methoden und ist sehr effizient. Wenn die Zahlenhaufen riesig sind und die Zahlen selbst klein, gewinnt bsort fast immer.

2. Die Praxis (Der Realitätscheck):
   Wenn man bsort auf modernen Computern mit großen Zahlen (64-Bit) testet, ist es nicht immer schneller als die bewährten Standard-Methoden. Warum?

   • Der „Verwirrte Chef": Der Computer muss bei jedem Schritt entscheiden: „Geh links oder rechts?". Bei zufälligen Daten ist diese Entscheidung oft unvorhersehbar (wie ein Lotteriespiel). Das verwirrt den Prozessor, der gerne vorher plant, was als Nächstes kommt.
   • Zu viel Treppensteigen: bsort geht sehr tief in die „Treppe" der Rekursion (es ruft sich selbst sehr oft auf). Das füllt den Arbeitsspeicher des Prozessors mit „Müll" (Stack-Pollution), während andere Methoden klüger sind und bei kleinen Gruppen einfachere, schnelle Methoden nutzen.
   • Zu viele Schritte: Um eine 64-Bit-Zahl zu sortieren, muss bsort den ganzen Haufen 64 Mal durchgehen. Andere Algorithmen brauchen oft weniger Durchgänge.

🚀 Fazit: Was lernen wir daraus?

Das Paper stellt bsort vor als eine clevere, mathematisch elegante Methode, die Zahlen sortiert, indem sie deren Binärcode direkt bearbeitet, statt sie zu vergleichen.

• Stärke: Es ist fantastisch für kleine Datenmengen oder kleine Zahlen (wie in eingebetteten Systemen oder bei einfachen Daten). Es ist speichereffizient und theoretisch sehr schnell.
• Schwäche: Bei riesigen Datenmengen mit großen Zahlen stolpert es über die Architektur moderner Computer (zu viele Verzweigungen, zu viel Treppensteigen).

Die große Erkenntnis:
Der Autor sagt im Grunde: „Ich habe einen neuen Motor gebaut, der theoretisch schneller ist als jeder Ferrari. Aber ich habe ihn noch nicht in die Karosserie eines modernen Autos eingebaut, der die Straßenbedingungen (den Computer) perfekt nutzt."

Die Zukunft von bsort liegt darin, es mit den Tricks der alten Meister zu kombinieren (Hybrid-Ansatz), um die Theorie endlich in die Praxis zu bringen. Es ist ein vielversprechender Kandidat für die nächste Generation von Sortieralgorithmen, besonders wenn wir lernen, wie man ihn besser an moderne Computer anpasst.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papiers über den bsort-Algorithmus auf Deutsch:

Titel: bsort: Ein theoretisch effizienter, nicht-vergleichsbasierter Sortieralgorithmus für Ganzzahlen und Gleitkommazahlen

Autor: Benjamín Guzmán (Forschender, Mexiko-Stadt; Arbeit vor der Tätigkeit bei Amazon durchgeführt)

---

1. Problemstellung

Das Sortieren ist ein fundamentales Problem der Informatik. Herkömmliche Algorithmen (wie Quicksort oder Mergesort) basieren auf dem Vergleichen von Elementenpaaren und haben eine untere Schranke der Worst-Case-Zeitkomplexität von $\Omega(n \log n)$.
Nicht-vergleichsbasierte Algorithmen (wie Radix-Sort) bieten lineare Laufzeit, haben jedoch oft Einschränkungen:

• Viele bitweise Algorithmen (z. B. Binäres Quicksort) funktionieren nur für gleich vorzeichenbehaftete Ganzzahlen.
• Erweiterungen für gemischte Vorzeichen oder Gleitkommazahlen erfordern oft zusätzlichen Speicherplatz (nicht-in-place) oder komplexe Trennverfahren.
• Es fehlt ein einheitlicher, in-place Algorithmus, der effizient mit vorzeichenbehafteten Ganzzahlen, vorzeichenlosen Ganzzahlen und Gleitkommazahlen (IEEE-754) umgehen kann.

2. Methodik und Algorithmus

Der vorgestellte bsort-Algorithmus ist eine modifizierte und verallgemeinerte Version des Binären Quicksorts. Er nutzt eine bitweise Partitionierung, um die Daten rekursiv zu sortieren, ohne direkte numerische Vergleiche durchzuführen.

Kernmechanismus

• Bitweise Partitionierung: Der Algorithmus durchläuft die Bits der Elemente von der höchstwertigen Stelle (MSB) zur niedrigstwertigen (LSB). In jedem Schritt wird das Array basierend auf dem aktuellen Bit in zwei Partitionen aufgeteilt (Bits mit 0 und Bits mit 1).
• In-Place-Operation: Die Partitionierung erfolgt durch Tauschen von Elementen innerhalb des ursprünglichen Arrays (ähnlich wie beim Lomuto- oder Hoare-Partitionierungsschema), was zusätzlichen Speicherplatz minimiert.

Anpassungen für verschiedene Datentypen

1. Vorzeichenbehaftete Ganzzahlen (Signed Integers):

   • Das Standard-Binäres Quicksort sortiert nach der lexikografischen Reihenfolge der Binärdarstellung. Bei Zweierkomplement führt dies dazu, dass negative Zahlen (MSB=1) fälschlicherweise als "größer" eingestuft werden als positive (MSB=0).
   • Lösung: bsort invertiert die Sortierreihenfolge für den allerersten Durchlauf (MSB). Dadurch werden negative Zahlen korrekt vor den positiven platziert. Für die nachfolgenden Bits wird die normale Reihenfolge beibehalten.

2. Gleitkommazahlen (Floating-Point / IEEE-754):

   • Gleitkommazahlen bestehen aus Vorzeichen ($s$), Exponent ($p$) und Mantisse ($m$). Eine einfache bitweise Sortierung versagt, da die numerische Ordnung nicht direkt der bitweisen Lexikografie entspricht (insbesondere bei negativen Exponenten und der Bias-Darstellung).
   • Lösung: Der Algorithmus führt einen sequenziellen, mehrstufigen Sortierprozess durch:
     1. Sortierung nach Vorzeichen: Trennung in negative und nicht-negative Zahlen (mit invertierter Richtung für den ersten Bit-Durchlauf).
     2. Sortierung nach Exponent: Innerhalb der Vorzeichen-Partitionen wird nach dem Exponenten sortiert. Wichtig: Für negative Zahlen muss die Exponenten-Sortierung umgekehrt werden (da ein größerer Exponent bei negativen Zahlen einen kleineren absoluten Wert bedeutet).
     3. Sortierung nach Mantisse: Da Vorzeichen und Exponent nun identisch sind, entspricht die Sortierung der Mantisse dem Sortieren von vorzeichenlosen Ganzzahlen.

3. Theoretische Analyse und Komplexität

• Zeitkomplexität: $O(w \cdot n)$, wobei $n$ die Anzahl der Elemente und $w$ die Wortgröße (Anzahl der Bits) ist.
  • Da $w$ für einen gegebenen Datentyp konstant ist (z. B. 32 oder 64), verhält sich der Algorithmus asymptotisch linear ($O(n)$).
• Speicherkomplexität: $O(w)$ zusätzlicher Speicherplatz.
  • Der Algorithmus ist in-place bezüglich $n$ (kein zusätzlicher Speicher proportional zur Eingabegröße).
  • Der rekursive Aufrufstapel benötigt $O(w)$ Platz, da die Rekursionstiefe durch die Bitbreite $w$ begrenzt ist.

4. Empirische Ergebnisse

Der Autor verglich bsort mit etablierten Algorithmen:

• Benchmarks: Introsort (C++ STL std::sort), Spreadsort, ska_sort (Radix-Sort) und Quicksort.
• Testumgebung: 64-bit Linux, Intel i5-8350U, verschiedene Datentypen (char bis double) und Array-Größen (bis $5 \cdot 10^9$).

Ergebnisse:

• Kleine Wortgrößen (z. B. 8-bit char): bsort übertrifft den hybriden Introsort konsistent, da die geringe Bittiefe ($w$) den Overhead der Rekursion minimiert.
• Große Wortgrößen (z. B. 64-bit long long oder double): bsort ist langsamer als Introsort und spezialisierte Radix-Algorithmen.
• Ursachen für Performance-Einbußen bei großen $w$:
  1. Branch Misprediction: Die bedingten Verzweigungen in der Partitionierungsschleife sind bei zufälligen Daten unvorhersehbar (~50% Fehlvorhersagen), was Pipeline-Flushes verursacht.
  2. Stack-Pollution & Cache-Misses: Die strikte rekursive Struktur führt zu hohem Registerdruck und vielen L1-D-Cache-Misses, da der Stack für tiefe Rekursionen genutzt wird, anstatt Daten im Cache zu halten.
  3. Instruktionsvolumen: bsort scannt das Array $w$-mal, während Introsort nur $O(\log n)$ Durchläufe benötigt. Bei 64-Bit-Daten bedeutet dies 64 vollständige Scans vs. ca. 26 für Introsort.

5. Schlüsselbeiträge

1. Einheitlicher Algorithmus: Bietet die erste in-place, nicht-vergleichsbasierte Lösung, die nahtlos vorzeichenbehaftete Ganzzahlen, vorzeichenlose Ganzzahlen und IEEE-754-Gleitkommazahlen sortiert.
2. Formale Korrektheitsbeweise: Der Autor liefert mathematische Beweise für die Notwendigkeit der Sortierreihenfolge (Vorzeichen $\to$ Exponent $\to$ Mantisse) bei Gleitkommazahlen und die Korrektheit des Algorithmus.
3. Theoretische vs. Praktische Lücke: Das Papier identifiziert präzise, warum ein theoretisch linearer Algorithmus in der Praxis bei großen Datentypen hinter hybriden Vergleichsalgorithmen zurückbleibt (Micro-Architektur-Bottlenecks wie Branch Prediction und Cache-Lokalität).

6. Bedeutung und Ausblick

• Bedeutung: bsort demonstriert, dass nicht-vergleichsbasierte Sortierung für spezifische Anwendungsfälle (kleine Datentypen, eingebettete Systeme mit begrenztem Speicher) eine hochleistungsfähige Alternative sein kann. Es liefert eine solide theoretische Basis für bitweises Sortieren komplexer Datentypen.
• Zukünftige Verbesserungen: Der Autor schlägt vor, bsort zu einem hybriden Algorithmus weiterzuentwickeln. Dies würde bedeuten, bei kleinen Partitionen zu iterativen, cache-freundlichen Methoden zu wechseln, SIMD-Instruktionen für Parallelisierung zu nutzen und verzweigungsfreie Partitionierung (Branchless) einzuführen, um die Performance bei großen Wortgrößen zu steigern.

Fazit: bsort ist ein elegantes, speichereffizientes Konzept mit theoretischem Potenzial für lineare Sortierung, dessen praktische Leistung jedoch derzeit durch die Architektur moderner Prozessoren (Branch Prediction, Cache-Hierarchie) begrenzt wird. Für kleine Datentypen ist es jedoch bereits wettbewerbsfähig.