Heltalssortering

Inom datavetenskap är heltalssortering det algoritmiska problemet med att sortera en samling datavärden efter heltalsnycklar . Algoritmer utformade för heltalssortering kan också ofta tillämpas på sorteringsproblem där nycklarna är flyttal , rationella tal eller textsträngar. Möjligheten att utföra heltalsaritmetik på nycklarna tillåter att heltalssorteringsalgoritmer är snabbare än jämförelsesorteringsalgoritmer i många fall, beroende på detaljerna om vilka operationer som är tillåtna i beräkningsmodellen och hur stora heltal som ska sorteras är.

Heltalssorteringsalgoritmer inklusive duvhålssortering , räknesortering och radixsortering används ofta och är praktiska. Andra heltalssorteringsalgoritmer med mindre värsta tänkbara tidsgränser tros inte vara praktiska för datorarkitekturer med 64 eller färre bitar per ord. Många sådana algoritmer är kända, med prestanda beroende på en kombination av antalet objekt som ska sorteras, antal bitar per nyckel och antal bitar per ord hos datorn som utför sorteringsalgoritmen.

Allmänna överväganden

Beräkningsmodeller

Tidsgränser för heltalssorteringsalgoritmer beror vanligtvis på tre parametrar: antalet $n$ datavärden som ska sorteras, storleken $K$ på den största möjliga nyckeln som ska sorteras och antalet $w$ bitar som kan representeras i ett enda maskinord av datorn på vilken algoritmen ska utföras. Typiskt antas det att $w \geq log2 (max(n, K))$ ; det vill säga att maskinord är tillräckligt stora för att representera ett index i sekvensen av indata, och även tillräckligt stora för att representera en enda nyckel.

Heltalssorteringsalgoritmer är vanligtvis utformade för att fungera i antingen pekarmaskinen eller datormodeller med direktåtkomst . Den största skillnaden mellan dessa två modeller är hur minnet kan adresseras. Direktåtkomstmaskinen tillåter vilket värde som helst som är lagrat i ett register att användas som adress för minnesläs- och skrivoperationer, med enhetskostnad per operation. Denna förmåga gör att vissa komplexa operationer på data kan implementeras snabbt med hjälp av tabelluppslagningar. I motsats till pekmaskinsmodellen använder läs- och skrivoperationer adresser lagrade i pekare, och det är inte tillåtet att utföra aritmetiska operationer på dessa pekare. I båda modellerna kan datavärden läggas till, och bitvisa booleska operationer och binära skiftoperationer kan vanligtvis också utföras på dem, i tidsenhet per operation. Olika heltalssorteringsalgoritmer gör dock olika antaganden om huruvida heltalsmultiplikation också är tillåten som en tidsenhetsoperation. Andra mer specialiserade beräkningsmodeller såsom den parallella direktåtkomstmaskinen har också övervägts.

Andersson, Miltersen & Thorup (1999) visade att i vissa fall kunde de multiplikationer eller tabelluppslagningar som krävs av vissa heltalssorteringsalgoritmer ersättas av skräddarsydda operationer som skulle vara lättare att implementera i hårdvara men som vanligtvis inte är tillgängliga på datorer för generella ändamål. Thorup (2003) förbättrade detta genom att visa hur man ersätter dessa speciella operationer med instruktionerna för bitfältsmanipulation som redan finns på Pentium- processorer.

I externa minnesmodeller av beräkningar är ingen känd heltalssorteringsalgoritm snabbare än jämförelsesortering. Forskare har visat att i dessa modeller kan begränsade klasser av algoritmer som är begränsade i hur de manipulerar sina nycklar inte vara snabbare än jämförelsesortering, och att en heltalssorteringsalgoritm som är snabbare än jämförelsesortering skulle antyda falskheten hos en standardförmodan i nätverkskodning .

Sortering kontra heltals prioritetsköer

En prioritetskö är en datastruktur för att upprätthålla en samling objekt med numeriska prioriteringar, med operationer för att hitta och ta bort objektet med det lägsta prioritetsvärdet. Jämförelsebaserade prioritetsköer som den binära högen tar logaritmisk tid per uppdatering, men andra strukturer som van Emde Boas-trädet eller hinkkön kan vara snabbare för indata vars prioriteringar är små heltal. Dessa datastrukturer kan användas i urvalssorteringsalgoritmen , som sorterar en samling av element genom att upprepade gånger hitta och ta bort det minsta elementet från samlingen, och returnera elementen i den ordning de hittades. En prioritetskö kan användas för att upprätthålla samlingen av element i denna algoritm, och tiden för denna algoritm på en samling av $n$ element kan begränsas av tiden för att initiera prioritetskön och sedan utföra $n$ sök- och borttagningsoperationer. Till exempel, att använda en binär hög som en prioritetskö i urvalssorteringen leder till högsorteringsalgoritmen , en jämförelsesorteringsalgoritm som tar $O (n log n)$ tid. Användning av urvalssortering med en hinkkö ger istället en form av duvhålssortering , och att använda van Emde Boas-träd eller andra heltalsprioritetsköer leder till andra snabba heltalssorteringsalgoritmer.

Istället för att använda en heltalsprioritetskö i en sorteringsalgoritm är det möjligt att gå åt andra hållet och använda heltalssorteringsalgoritmer som subrutiner inom en heltalsprioritetsködatastruktur. Thorup (2007) använde denna idé för att visa att om det är möjligt att utföra heltalssortering i tid $T (n)$ per nyckel, så gäller samma tidsgräns för tiden per insättning eller raderingsoperation i en prioriterad ködatastruktur. Thorups reduktion är komplicerad och förutsätter tillgången till antingen snabba multiplikationsoperationer eller tabelluppslagningar, men han tillhandahåller också en alternativ prioritetskö med endast addition och booleska operationer med tiden T ( n ) $+ T (log n) + T (log n) + ...$ per operation, som högst multiplicerar tiden med en itererad logaritm .

Användbarhet

De klassiska heltalssorteringsalgoritmerna för duvhålssortering , räknesortering och radixsortering används ofta och är praktiska. Mycket av den efterföljande forskningen om heltalssorteringsalgoritmer har fokuserat mindre på praktiska och mer på teoretiska förbättringar i deras värsta fall-analys, och algoritmerna som kommer från denna forskningslinje anses inte vara praktiska för nuvarande 64-bitars datorarkitekturer, även om experiment har visat att några av dessa metoder kan vara en förbättring av radixsortering för data med 128 eller fler bitar per nyckel. Dessutom, för stora datamängder, kan de nästan slumpmässiga minnesåtkomstmönstren för många heltalssorteringsalgoritmer handikappa dem jämfört med jämförelsesorteringsalgoritmer som har utformats med minneshierarkin i åtanke.

Heltalssortering ger ett av de sex riktmärkena i DARPA High Productivity Computing Systems Discrete Mathematics benchmark-svit, och ett av elva riktmärken i NAS Parallel Benchmarks- sviten.

Praktiska algoritmer

$0$ Duvhålssortering eller räknesortering kan båda sortera $n$ dataobjekt som har nycklar i intervallet från till $K -1$ i tiden $O (n + K)$ . I duvhålssortering (ofta kallad hinksortering) distribueras pekare till dataobjekten till en tabell med hinkar, representerade som insamlingsdatatyper såsom länkade listor , med hjälp av nycklarna som index i tabellen. Sedan sammanfogas alla hinkar för att bilda utdatalistan. Räkna sortering använder en tabell med räknare i stället för en tabell med hinkar, för att bestämma antalet föremål med varje nyckel. Sedan används en prefixsummaberäkning för att bestämma intervallet av positioner i den sorterade utgången där värdena med varje nyckel ska placeras. Slutligen, i en andra passage över ingången, flyttas varje objekt till sin nyckelposition i utmatningsfältet. Båda algoritmerna involverar endast enkla slingor över ingångsdata (tar tid $O (n)$ ) och över uppsättningen möjliga nycklar (tar tid $O (K)$ ), vilket ger deras $O (n + K)$ totala tidsgräns.

$0$ Radix-sortering är en sorteringsalgoritm som fungerar för större nycklar än duvhålssortering eller räknesortering genom att utföra flera passeringar över data. Varje pass sorterar inmatningen med endast en del av nycklarna, genom att använda en annan sorteringsalgoritm (som t.ex. duvhålssortering eller räknesortering) som endast lämpar sig för små nycklar. För att dela upp tangenterna i delar, beräknar radixsorteringsalgoritmen positionsbeteckningen för varje tangent, enligt någon vald radix ; sedan är den del av nyckeln som används för det $i:$ te passet av algoritmen den $i:$ te siffran i positionsbeteckningen för den fullständiga nyckeln, med början från den minst signifikanta siffran och går vidare till den mest signifikanta. För att den här algoritmen ska fungera korrekt måste sorteringsalgoritmen som används vid varje pass över data vara stabil : objekt med lika siffror ska inte byta position med varandra. För största effektivitet bör radixen väljas så att den ligger nära antalet dataposter, $n$ . Genom att använda en potens av två nära $n$ som radix kan dessutom nycklarna för varje pass beräknas snabbt med endast snabba binära skift- och maskoperationer. Med dessa val, och med duvhålssortering eller räknesortering som basalgoritm, kan radixsorteringsalgoritmen sortera $n$ dataobjekt som har nycklar i intervallet från till $K - 1$ i tiden $O (n log n K)$ .

Teoretiska algoritmer

Många heltalssorteringsalgoritmer har utvecklats vars teoretiska analys visar att de beter sig bättre än jämförelsesortering, duvhålssortering eller radixsortering för tillräckligt stora kombinationer av parametrarna som definierar antalet objekt som ska sorteras, nyckelomfång och maskinordstorlek. Vilken algoritm som har bäst prestanda beror på värdena för dessa parametrar. Men trots sina teoretiska fördelar är dessa algoritmer inte en förbättring för de typiska intervallen för dessa parametrar som uppstår i praktiska sorteringsproblem.

Algoritmer för små nycklar

$0$ Ett Van Emde Boas-träd kan användas som en prioritetskö för att sortera en uppsättning av $n$ nycklar, var och en i intervallet från till $K - 1$ , i tiden $O (n log log K)$ . Detta är en teoretisk förbättring jämfört med radixsortering när $K$ är tillräckligt stor. Men för att använda ett Van Emde Boas-träd behöver man antingen ett direkt adresserbart minne av $K$ -ord, eller så behöver man simulera det med hjälp av en hashtabell , vilket minskar utrymmet till linjärt men gör att algoritmen slumpas. En annan prioriterad kö med liknande prestanda (inklusive behovet av randomisering i form av hashtabeller) är Y-fast trie av Willard (1983) .

En mer sofistikerad teknik med liknande smak och med bättre teoretisk prestanda utvecklades av Kirkpatrick & Reisch (1984) . De observerade att varje pass av radixsortering kan tolkas som en avståndsreduktionsteknik som i linjär tid reducerar den maximala nyckelstorleken med en faktor $n$ ; istället reducerar deras teknik nyckelstorleken till kvadratroten av dess tidigare värde (halverar antalet bitar som behövs för att representera en nyckel), återigen i linjär tid. Som i radixsortering tolkar de nycklarna som tvåsiffriga bas- $b-$ tal för en bas $b$ som är ungefär $\sqrt K$ . De grupperar sedan objekten som ska sorteras i hinkar enligt deras höga siffror, i linjär tid, med antingen ett stort men oinitierat direktadresserat minne eller en hashtabell. Varje hink har en representant, föremålet i hinken med den största nyckeln; de sorterar sedan listan med poster med hjälp av de höga siffrorna för representanterna och de låga siffrorna för de icke-representanter som nycklar. Genom att gruppera objekten från denna lista i hinkar igen, kan varje hink placeras i sorterad ordning, och genom att extrahera representanterna från den sorterade listan kan hinkarna sammanfogas i sorterad ordning. Sålunda, i linjär tid, reduceras sorteringsproblemet till ett annat rekursivt sorteringsproblem där nycklarna är mycket mindre, kvadratroten av deras tidigare storlek. Att upprepa denna intervallreduktion tills nycklarna är tillräckligt små för att sortera i hink leder till en algoritm med körtid $O(n log log n K)$ .

En komplicerad randomiserad algoritm av Han & Thorup (2002) i ordet RAM -beräkningsmodell tillåter dessa tidsgränser att reduceras ännu längre, till $O(n \sqrt log log K)$ .

Algoritmer för stora ord

En heltalssorteringsalgoritm sägs vara $icke log max(n , K)$ -konservativ om den kräver en ordstorlek $w$ som är betydligt större än . Som ett extremt exempel, om $w \geq K$ , och alla nycklar är distinkta, kan uppsättningen nycklar sorteras i linjär tid genom att representera den som en bitvektor , med en 1 bit i position $i$ när $i$ är en av inmatningsnycklarna, och sedan upprepade gånger ta bort den minst signifikanta biten.

Den icke-konservativa packade sorteringsalgoritmen av Albers & Hagerup (1997) använder en subrutin, baserad på Ken Batchers bitoniska sorteringsnätverk , för att slå samman två sorterade sekvenser av nycklar som var och en är tillräckligt kort för att packas i ett enda maskinord. Indata till den packade sorteringsalgoritmen, en sekvens av objekt lagrade en per ord, omvandlas till en packad form, en sekvens av ord som vart och ett innehåller flera artiklar i sorterad ordning, genom att använda denna subrutin upprepade gånger för att fördubbla antalet objekt som packas i varje ord. När sekvensen väl är i packad form använder Albers och Hagerup en form av sammanfogad sortering för att sortera den; när två sekvenser slås samman för att bilda en enda längre sekvens, kan samma bitoniska sorteringssubrutin användas för att upprepade gånger extrahera packade ord som består av de minsta återstående elementen av de två sekvenserna. Den här algoritmen får tillräckligt med snabbhet från sin packade representation för att sortera dess indata i linjär tid närhelst det är möjligt för ett enda ord att innehålla $Ω(log n log log n)$ nycklar; det vill säga när $log K log n log log n \leq cw$ för någon konstant $c > 0$ .

Algoritmer för få föremål

Duvhålssortering, räknesortering, radixsortering och Van Emde Boas trädsortering fungerar alla bäst när nyckelstorleken är liten; för tillräckligt stora nycklar blir de långsammare än jämförelsesorteringsalgoritmer. Men när nyckelstorleken eller ordstorleken är mycket stor i förhållande till antalet objekt (eller motsvarande när antalet artiklar är litet), kan det återigen bli möjligt att sortera snabbt med hjälp av olika algoritmer som drar fördel av den inneboende parallelliteten i förmågan att utföra aritmetiska operationer på stora ord.

Ett tidigt resultat i denna riktning gavs av Ajtai, Fredman & Komlós (1984) med hjälp av cellsondsmodellen för beräkning (en artificiell modell där komplexiteten hos en algoritm endast mäts av antalet minnesåtkomster den utför). Byggande på sitt arbete Fredman & Willard (1994) två datastrukturer, Q-högen och atomhögen, som är implementerbara på en direktåtkomstmaskin. Q-heapen är en bitparallell version av ett binärt försök och tillåter både prioriterade köoperationer och efterföljare och föregångare att utföra i konstant tid för uppsättningar av $O ((log N) 1/4)$ objekt, där $N \leq 2 w$ är storleken på de förberäknade tabellerna som behövs för att implementera datastrukturen. Atomhögen är ett B-träd där varje trädnod representeras som en Q-hög; det tillåter köoperationer med konstant tidsprioritet (och därför sortering) för uppsättningar av ( $log N) O (1)$ objekt.

Andersson et al. (1998) tillhandahåller en randomiserad algoritm som kallas signatursortering som tillåter linjär tidssortering av uppsättningar av upp till $2 O ((log w) 1/2 - ε)$ objekt åt gången, för varje konstant $ε > 0$ . Liksom i Kirkpatricks och Reischs algoritm utför de intervallreduktion med hjälp av en representation av nycklarna som tal i basen $b$ för ett noggrant val av $b$ . Deras avståndsreduktionsalgoritm ersätter varje siffra med en signatur, vilket är ett hashat värde med $O (log n)$ bitar så att olika siffervärden har olika signaturer. Om $n$ är tillräckligt litet kommer talen som bildas av denna ersättningsprocess att vara betydligt mindre än de ursprungliga nycklarna, vilket gör att den icke-konservativa packade sorteringsalgoritmen enligt Albers & Hagerup (1997) kan sortera de ersatta talen i linjär tid. Från den sorterade listan med ersatta siffror är det möjligt att bilda ett komprimerat försök av nycklarna i linjär tid, och barnen för varje nod i försöket kan sorteras rekursivt med endast nycklar av storlek $b$ , varefter en trädpassering ger sorterad ordning på föremålen.

Transdikotoma algoritmer

Fredman & Willard (1993) introducerade den transdikotoma analysmodellen för heltalssorteringsalgoritmer, där ingenting antas om heltalsnycklarnas omfång och man måste binda algoritmens prestanda genom en funktion av enbart antalet datavärden. Alternativt, i denna modell, antas körtiden för en algoritm på en uppsättning av $n$ objekt vara den värsta körtiden för alla möjliga kombinationer av värden på $K$ och $w$ . Den första algoritmen av denna typ var Fredman $O(n log n / log log n ) och$ Willards sorteringsalgoritm för fusionsträd , som körs i tiden ; detta är en förbättring jämfört med jämförelsesortering för alla val av $K$ och $w$ . En alternativ version av deras algoritm som inkluderar användningen av slumptal och heltalsdivisionsoperationer förbättrar detta till $O( n \sqrt log n)$ .

Sedan deras arbete har ännu bättre algoritmer utvecklats. Till exempel, genom att upprepade gånger använda Kirkpatrick–Reisch intervallreduktionsteknik tills nycklarna är tillräckligt små för att tillämpa den packade sorteringsalgoritmen Albers–Hagerup, är det möjligt att sortera i tid O $(n log log n)$ ; avståndsreduktionsdelen av denna algoritm kräver dock antingen ett stort minne (proportionellt mot $\sqrt K$ ) eller randomisering i form av hashtabeller.

Han & Thorup (2002) visade hur man sorterar i randomiserad tid $O(n \sqrt log log n)$ . Deras teknik innebär att man använder idéer relaterade till signatursortering för att dela upp data i många små underlistor, av en storlek som är tillräckligt liten för att signatursortering kan sortera var och en av dem effektivt. Det är också möjligt att använda liknande idéer för att sortera heltal deterministiskt i tid $O (n log log n)$ och linjärt rum. Genom att endast använda enkla aritmetiska operationer (inga multiplikationer eller tabelluppslag) är det möjligt att sortera i randomiserad förväntad tid $O (n log log n)$ eller deterministiskt i tid $O (n (log log n) 1 + ε)$ för vilken konstant $ε > 0 som helst$ .

Fotnoter

Sekundära källor

Chowdhury, Rezaul A. (2008), "Equivalence between priority queues and sorting" , i Kao, Ming-Yang (red.), Encyclopedia of Algorithms , Springer, s. 278–281, ISBN 9780387307701 .
Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001), Introduction to Algorithms (2nd ed.), MIT Press och McGraw-Hill , ISBN 0-262-03293-7 .
Goodrich, Michael T. ; Tamassia, Roberto (2002), "4.5 Bucket-Sort and Radix-Sort", Algorithm Design: Foundations, Analysis, and Internet Examples , John Wiley & Sons, s. 241–243 .

Primära källor

Aggarwal, Alok; Vitter, Jeffrey S. (september 1988), "The input/output complexity of sorting and related problems", Communications of the ACM , 31 (9): 1116–1127, doi : 10.1145/48529.48535 , S2CID 6264984
Ajtai, M .; Fredman, M. ; Komlós, J. (1984), "Hashfunktioner för prioriterade köer", Information and Control , 63 (3): 217–225, doi : 10.1016/S0019-9958(84)80015-7 , MR 0837087 .
Albers, Susanne ; Hagerup, Torben (1997), "Förbättrad parallell heltalssortering utan samtidig skrivning", Information and Computation , 136 ( 1 ) : 25–51, CiteSeerX 10.1.1.53.498 , doi : 10.1006 /inco.1997.2914 , 7C .
Andersson, Arne; Hagerup, Torben; Nilsson, Stefan; Raman, Rajeev (1998), "Sortering i linjär tid?", Journal of Computer and System Sciences , 57 (1): 74–93, doi : 10.1006/jcss.1998.1580 , MR 1649809 .
Andersson, Arne; Nilsson, Stefan (1998), " Implementing radixsort", ACM Journal of Experimental Algorithmics , 3 : 7–es, CiteSeerX 10.1.1.54.4536 , doi : 10.1145/297096.297136 , 17C 69 17 , 17C 69 17. 17C 69 17 .
Andersson, Arne; Miltersen, Peter Bro; Thorup, Mikkel (1999), "Fusionsträd kan endast implementeras med $AC- 0$ instruktioner", Theoretical Computer Science , 215 (1–2): 337–344, CiteSeerX 10.1.1.32.9401 , doi : 10.1016/S0304-3975(9975) )00172-8 , MR 1678804 .
Bhatt, PCP; Diks, K.; Hagerup, T.; Prasad, VC; Radzik, T.; Saxena, S. (1991), "Förbättrad deterministisk parallell heltalssortering", Information and Computation , 94 (1): 29–47, doi : 10.1016/0890-5401(91)90031-V , MR 1123154 .
Cole, R.; Vishkin, U. (1986), "Deterministic coin tossing with applications to optimal parallell list ranking", Information and Control , 70 (1): 32–53, doi : 10.1016/S0019-9958(86)80023-7 .
Comrie, LJ (1929–1930), "The Hollerith and Powers tabulating machines", Trans. Office Mach. Users' Assoc., LTD. : 25–37 . Citerad av Thorup (2007) som en tidig källa för radixsortering .
Farhadi, Alireza; Hajiaghayi, Mohammad Taghi ; Larsen, Kasper Green; Shi, Elaine (september 2020), "Lower bounds for extern minnesheltalssortering via nätverkskodning", Communications of the ACM , 63 (10): 97–105, arXiv : 1811.01313 , doi : 10.1145/34162CID 52, 381 S2268 52 , 3816268 52 .
Fredman, Michael L. ; Willard, Dan E. (1993), "Surpassing the information-theoretic bound with fusion trees", Journal of Computer and System Sciences , 47 (3): 424–436, doi : 10.1016/0022-0000(93)90040-4 MR 1248864 . _
Fredman, Michael L. ; Willard, Dan E. (1994), "Trans-dichotomous algorithms for minimum spaning trees and shortest paths", Journal of Computer and System Sciences , 48 (3): 533–551, doi : 10.1016/S0022-0000(05)80064 -9 , MR 1279413 .
Hagerup, Torben (1987), "Mot optimal parallell skopsortering", Information and Computation , 75 (1): 39–51, doi : 10.1016/0890-5401(87)90062-9 , MR 0910976 .
Han, Yijie (2004), "Deterministic sortering in $O (n log log n)$ time and linear space", Journal of Algorithms , 50 (1): 96–105, doi : 10.1016/j.jalgor.2003.09.001 , MR 2028585 .
Han, Yijie; Thorup, M. (2002), "Integer sortering i $O(n \sqrt log log n)$ förväntad tid och linjärt rum", Proceedings of the 43rd Annual Symposium on Foundations of Computer Science (FOCS 2002) , IEEE Computer Society, s. 135 –144, doi : 10.1109/SFCS.2002.1181890 , S2CID 5245628 .
Kirkpatrick, David ; Reisch, Stefan (1984), "Övre gränser för sortering av heltal på direktåtkomstmaskiner", Theoretical Computer Science , 28 (3): 263–276, doi : 10.1016/0304-3975(83)90023-3 , MR 0742289 .
McIlroy, Peter M.; Bostic, Keith; McIlroy, M. Douglas (1993), "Engineering Radix Sort" (PDF) , Computing Systems , 6 (1): 5–27 .
Pedersen, Morten Nicolaj (1999), En studie av den praktiska betydelsen av ord-RAM-algoritmer för intern heltalssortering , Magisteruppsats, Institutionen för datavetenskap, Köpenhamns universitet, Danmark, arkiverad från originalet 2012-03-16 , hämtad 2011 -04-21 .
Rahman, Naila; Raman, Rajeev (1998), "An experimental study of word-level parallelism in some sorting algorithms", Algorithm Engineering, 2nd International Workshop, WAE '92, Saarbrücken, Tyskland, 20–22 augusti 1998, Proceedings ( PDF) , Max Planck-institutet för datavetenskap, s. 193–203 .
Reif, John H. (1985), "En optimal parallell algoritm för heltalssortering", Proceedings of the 26th Annual Symposium on Foundations of Computer Science (FOCS 1985), IEEE Computer Society, s. 496–504, doi : 10.1109/SFCS .1985.9 , S2CID 5694693 .
Thorup, Mikkel (2002), "Randomiserad sortering i $O (n log log n)$ time and linear space using addition, shift och bitvisa booleska operationer", Journal of Algorithms , 42 (2): 205–230, CiteSeerX 10.1 .1.55.4443 , doi : 10.1006/jagm.2002.1211 , MR 1895974 , S2CID 9700543 .
Thorup, Mikkel (2003), "On $AC 0$ implementations of fusion trees and atomic heaps", Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, MD, 2003) , New York: ACM, s. 699–707, MR 1974982 .
Thorup, Mikkel (2007), "Ekvivalens mellan prioriterade köer och sortering", Journal of the ACM , 54 (6): Art. 28, doi : 10.1145/1314690.1314692 , MR 2374029 .
Willard, Dan E. (1983), "Log-logarithmic worst-case range queries are possible in space $Θ(N)$ ", Information Processing Letters , 17 (2): 81–84, doi : 10.1016/0020-0190(83) )90075-3 , MR 0731126 .