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

Dit artikel introduceert bsort, een niet-comparatief sorteeralgoritme voor gehele getallen en floating-point waarden dat via een benadering afgeleid van binaire quicksort een asymptotische looptijd van $O(wn)$ en een extra ruimtecomplexiteit van $O(w)$ bereikt, met prestaties die concurreren met geoptimaliseerde hybride algoritmen voor gegevens met kleine woordgroottes.

De kern

Hier is een uitleg van het artikel over bsort, vertaald naar eenvoudig Nederlands met creatieve vergelijkingen.

Wat is bsort?

Stel je voor dat je een enorme stapel papieren moet sorteren. De meeste mensen gebruiken een methode waarbij ze twee papieren naast elkaar houden en vragen: "Is deze groter dan die?" Dit noemen we vergelijkende sortering. Het is slim, maar het kost tijd, vooral als je duizenden papieren hebt.

bsort is een nieuwe, slimme manier om te sorteren die niet kijkt naar welke getal groter is. In plaats daarvan kijkt het naar de bouwstenen van de getallen zelf: de bits (de 0-en en 1-en waar computers van gemaakt zijn).

Het is alsof je niet vraagt "Wie is ouder?", maar je kijkt direct naar hun geboortedatum op hun identiteitskaart en sorteert ze op basis van de dag, de maand en het jaar.

Hoe werkt het? (De Grote Vergelijking)

1. Voor gewone getallen (Integers)

Stel je een rij mensen voor die in een donkere zaal staan. Ze hebben allemaal een lantaarn aan hun hoofd.

• De oude methode: Iedereen roept naar elkaar: "Ben jij ouder dan ik?" en wisselt van plek als dat zo is.
• De bsort-methode: De leraar (het algoritme) zegt: "Iedereen met een rode lantaarn naar links, iedereen met een blauwe lantaarn naar rechts."
  • Dan kijkt hij naar de volgende lantaarn (een andere kleur) en herhaalt hij het proces voor de groep links en de groep rechts.
  • Hij doet dit totdat iedereen op zijn plek staat.

Dit werkt razendsnel omdat je niet hoeft te praten (vergelijken), maar alleen hoeft te kijken naar één eigenschap (de kleur van de lantaarn).

2. Het probleem met min- en plus-getallen (Signed Integers)

Hier wordt het lastig. In de computerwereld zien negatieve getallen er anders uit dan positieve. Als je gewoon op de lantaarns kijkt, denkt de computer dat een negatief getal (dat begint met een '1' in zijn code) groter is dan een positief getal (dat begint met een '0'). Dat is natuurlijk fout! Een -5 is kleiner dan +5.

De oplossing van bsort:
De eerste keer dat de leraar de groepen verdeelt, doet hij het omgekeerd. Hij zegt: "Negatieve getallen (rode lantaarn) gaan naar links, positieve naar rechts." Zodra die grote groepen gescheiden zijn, kan hij normaal verder gaan met de rest van de lantaarns. Het is alsof je eerst de kinderen in de klas in twee groepen deelt: "Die met een hoed" en "Die zonder hoed", en dan pas binnen die groepen op lengte sorteert.

3. Voor zwevende komma's (Floating Point / Decimale getallen)

Decimale getallen (zoals 3.14 of -2.5) zijn nog ingewikkelder. Ze hebben drie onderdelen:

1. Het teken (plus of min).
2. De exponent (hoe groot is het getal? Is het 100 of 0.01?).
3. De mantisse (de precieze cijfers, zoals .14).

bsort doet dit in drie duidelijke rondes, net als het sorteren van brieven:

1. Ronde 1 (Het teken): Eerst scheidt hij alle negatieve brieven van de positieve.
2. Ronde 2 (De grootte): Binnen de negatieve groep sorteert hij op grootte (maar dan in omgekeerde volgorde, want -100 is kleiner dan -1). Binnen de positieve groep doet hij hetzelfde, maar dan normaal.
3. Ronde 3 (De details): Als de grootte gelijk is, sorteert hij pas op de laatste cijfers.

Dit zorgt ervoor dat -2.5 netjes tussen -3 en -2 terechtkomt, zonder dat de computer hoeft te rekenen.

Is het sneller dan alles wat we nu hebben?

Theoretisch: Ja, heel erg.
Het artikel zegt dat bsort lineair groeit. Als je 10 keer meer getallen hebt, duurt het 10 keer zo lang. Dat is perfect. De oude methodes worden trager naarmate de lijst groter wordt (ze moeten steeds vaker vergelijken).

In de praktijk: Het hangt af van de grootte.

• Kleine getallen (zoals 8-bit): bsort is een sprintkampioen. Het is sneller dan de beste methodes die nu in computers zitten.
• Grote getallen (zoals 64-bit): Hier wordt bsort een beetje traag. Waarom?
  • De "trap" van herhaling: bsort is heel strikt. Het blijft steeds terug naar de trap lopen om de volgende lantaarn te checken, tot op het allerlaatste bitje.
  • Andere methodes zijn flexibeler: De huidige kampioenen (zoals Introsort) zijn slimme hybrides. Als de stapel papier klein wordt, stoppen ze met het moeilijke werk en gebruiken ze een snellere, simpele methode. bsort doet het moeilijke werk tot het einde toe.
  • Cache-problemen: bsort loopt steeds door het hele geheugen heen, wat de computer een beetje in de war brengt (het moet vaak nieuwe informatie ophalen uit het geheugen).

Conclusie in één zin

bsort is een briljante, wiskundig perfecte methode om getallen te sorteren door naar hun bouwstenen te kijken. Het is de snelste auto op een korte, rechte baan (kleine getallen), maar op een lange, bochtige weg (grote, complexe getallen) heeft hij nog wat werk nodig om even snel te zijn als de hybride auto's die we nu gebruiken.

Het artikel suggereert dat als we bsort een beetje "slimmer" maken (bijvoorbeeld door te stoppen met recursie als de groepen klein genoeg zijn), het misschien wel de nieuwe koning van het sorteren kan worden.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "bsort: A theoretically efficient non-comparison-based sorting algorithm for integer and floating-point numbers" in het Nederlands.

Titel: bsort: Een theoretisch efficiënt niet-comparatief sorteer-algoritme voor gehele en zwevende-kommagetallen

Auteur: Benjamín Guzmán (Onafhankelijk onderzoeker, Mexico)

---

1. Het Probleem

Sorteren is een fundamenteel probleem in de informatica. Traditionele algoritmen (zoals Quicksort of Mergesort) zijn comparatief en hebben een ondergrens van $\Omega(n \log n)$ voor de tijdcomplexiteit in het slechtste geval.
Niet-comparatieve algoritmen, zoals Radix Sort, kunnen lineaire tijdcomplexiteit $O(n)$ bereiken, maar hebben vaak beperkingen:

• Veel zijn niet in-place (ze vereisen extra geheugen).
• Bestaande bit-niveau algoritmen (zoals Binary Quicksort) werken vaak alleen voor positieve gehele getallen of vereisen aparte behandelingen voor negatieve getallen en zwevende-kommagetallen (floats).
• Er ontbreekt een unificatie: een enkel algoritme dat in-place werkt en zowel voor tekens (signed/unsigned integers) als zwevende-kommagetallen (IEEE-754) correct sorteert.

2. Methodologie

De auteur introduceert bsort, een algoritme dat een aangepaste versie van Binary Quicksort gebruikt als kernmechanisme. Het algoritme sorteert door de bits van de elementen te analyseren, beginnend bij het meest significante bit (MSB).

Kernmechanismen:

• Bit-partitionering: Het algoritme verdeelt het array recursief op basis van de huidige bit (masker). Elementen met een '0' op die bitpositie worden gescheiden van elementen met een '1'.
• Unificatie van datatypen:
  • Tekens (Signed Integers): In twee-complement notatie heeft een negatief getal een MSB van 1, terwijl een positief getal een 0 heeft. Een standaard bit-partitionering zou negatieve getallen dus "na" de positieve plaatsen (wat verkeerd is voor oplopende sortering). Oplossing: bsort keert de sorteerrichting om voor de eerste pass (MSB) om negatieve getallen correct voor de positieve te plaatsen.
  • Zwevende-kommagetallen (Floats): Volgens IEEE-754 bestaat een float uit een tekenbit, exponent en mantisse. Het algoritme sorteert deze componenten hiërarchisch:
    1. Teken (Sign): Eerst gescheiden (negatief vs. positief).
    2. Exponent: Binnen elke teken-groep wordt gesorteerd op de exponent. Cruciaal: Voor negatieve getallen moet de exponent in aflopende volgorde worden gesorteerd (omdat een grotere exponent bij een negatief getal een kleiner getal betekent), terwijl positieve getallen in oplopende volgorde worden gesorteerd.
    3. Mantisse: Tot slot wordt gesorteerd op de mantisse (wat neerkomt op het sorteren van ongetekende gehele getallen).

Complexiteit:

• Tijd: $O(w \cdot n)$, waarbij $n$ het aantal elementen is en $w$ de woordgrootte (aantal bits). Voor een vast datatype (bijv. 64-bit) is dit lineair $O(n)$.
• Geheugen: $O(w)$ extra ruimte (voornamelijk voor de recursiestapel), wat betekent dat het in-place is ten opzichte van de invoergrootte $n$.

3. Belangrijkste Bijdragen

1. Unificatie: Het eerste algoritme dat in-place, niet-comparatief sorteren biedt voor een breed scala aan datatypen: signed/unsigned integers en IEEE-754 floats, binnen één enkel raamwerk.
2. Formele Bewijzen: De auteur levert formele bewijzen voor de correctheid van de sorteerorde (teken $\to$ exponent $\to$ mantisse) en de noodzaak van deze specifieke volgorde.
3. Theoretische Efficiëntie: Het demonstreert dat voor kleine woordgroottes (zoals 8-bit) en grote datasets, het algoritme theoretisch superieur is aan vergelijkende algoritmen ($O(n)$ vs $O(n \log n)$).

4. Resultaten (Empirische Analyse)

De auteur vergeleek bsort met state-of-the-art algoritmen: Introsort (C++ STL std::sort), Spreadsort en Radix Sort (ska_sort).

• Theoretische Voorspelling vs. Realiteit:
  • Voor kleine woordgroottes (bijv. char, 8-bit) presteert bsort beter dan Introsort, wat de theoretische voorspelling bevestigt.
  • Voor grote woordgroottes (bijv. long long, 64-bit of double) presteert bsort slechter dan de hybride algoritmen.
• Oorzaken van prestatieverlies bij grote $w$:
  1. Takvoorspelling (Branch Misprediction): De bit-partitionering bevat conditionele checks die bij willekeurige data onvoorspelbaar zijn (50% mispredict rate), wat leidt tot pipeline flushes.
  2. Stack Pollution & Register Pressure: Het algoritme gebruikt een rigide recursieve structuur tot op het laatste bit. Dit veroorzaakt veel contextswitjes en cache-misses (L1 D-cache), terwijl hybride algoritmen bij kleine partiities overschakelen naar iteratieve methoden.
  3. Instruction Volume: bsort scant het volledige array $w$ keer. Voor 64-bit getallen zijn dit 64 scans, terwijl Introsort slechts ongeveer $\log_2(n)$ scans nodig heeft (bijv. ~26 voor $10^8$ elementen).
• Conclusie van de tests: Hoewel bsort theoretisch efficiënt is, wordt de praktische prestatie beperkt door micro-architecturale factoren (cache-locality en branch prediction) in vergelijking met geoptimaliseerde hybride bibliotheken.

5. Betekenis en Toekomstperspectief

• Significantie: Het paper biedt een elegante, wiskundig onderbouwde oplossing voor het sorteren van gemengde datatypen zonder extra geheugen. Het benadrukt dat de theoretische complexiteit ($O(w \cdot n)$) niet altijd direct vertaalt naar de snelste uitvoeringstijd op moderne hardware zonder extra optimalisaties.
• Toekomstige Verbeteringen: De auteur stelt voor om bsort te transformeren tot een hybride algoritme. Dit zou inhouden dat het algoritme overschakelt naar niet-recursieve, cache-vriendelijke methoden zodra partiities een bepaalde grootte bereiken. Ook het gebruik van SIMD-instructies en branchless partitioning (conditional moves) wordt voorgesteld om de prestaties voor grote woordgroottes te verbeteren.

Samenvattend: bsort is een theoretisch krachtig, in-place algoritme dat de barrière tussen gehele getallen en floats doorbreekt. Hoewel het momenteel niet de snelste is voor grote 64-bit datasets vanwege hardware-beperkingen, biedt het een sterke basis voor toekomstige architecturale optimalisaties.