Třídění celých čísel - Integer sorting

Ve vědě o počítačích , integer třídění je algoritmické problém třídění kolekci datových hodnot pomocí celočíselných klíčů. Algoritmy určené pro třídění celých čísel lze také často aplikovat na problémy s tříděním, ve kterých jsou klíči čísla s plovoucí desetinnou čárkou , racionální čísla nebo textové řetězce. Schopnost provádět celočíselnou aritmetiku na klíčích umožňuje, aby byly algoritmy řazení celých čísel v mnoha případech rychlejší než algoritmy pro srovnávací řazení , v závislosti na podrobnostech, jaké operace jsou v modelu výpočtu povoleny a jak velká jsou celá čísla, která mají být tříděna.

Algoritmy třídění celých čísel včetně třídění holubů , počítání a radix jsou široce používány a praktické. Jiné algoritmy třídění celých čísel s menšími časovými limity nejhoršího případu se nepovažují za praktické pro počítačové architektury se 64 nebo méně bity na slovo. Je známo mnoho takových algoritmů, jejichž výkon závisí na kombinaci počtu položek, které mají být tříděny, počtu bitů na klíč a počtu bitů na slovo počítače provádějícího algoritmus řazení.

Obecné úvahy

Modely výpočtu

Časové limity pro algoritmy třídění celých čísel obvykle závisí na třech parametrech: počet $n$ datových hodnot, které mají být tříděny, velikost $K$ největšího možného klíče, který má být tříděn, a počet $w$ bitů, které lze reprezentovat v jednom strojovém slově počítač, na kterém má být algoritmus proveden. Typicky se předpokládá, že $w \geq log 2 (max (n, K))$ ; to znamená, že strojová slova jsou dostatečně velká, aby představovala rejstřík do posloupnosti vstupních dat, a také dostatečně velká, aby představovala jeden klíč.

Algoritmy třídění celých čísel jsou obvykle navrženy tak, aby fungovaly v modelech počítačů s ukazatelem nebo v strojích s náhodným přístupem . Hlavní rozdíl mezi těmito dvěma modely je v tom, jak lze adresovat paměť. Stroj s náhodným přístupem umožňuje použít jakoukoli hodnotu, která je uložena v registru, jako adresu operací čtení a zápisu paměti s jednotkovými náklady na operaci. Tato schopnost umožňuje rychle implementovat určité složité operace s daty pomocí vyhledávání tabulek. Naproti tomu v modelu ukazovacího stroje operace čtení a zápisu používají adresy uložené v ukazatelích a není povoleno provádět aritmetické operace s těmito ukazateli. V obou modelech mohou být přidány hodnoty dat a bitové booleovské operace a operace binárního posunu na nich mohou být obvykle také prováděny v jednotkovém čase na operaci. Různé algoritmy třídění celých čísel vytvářejí různé předpoklady o tom, zda je celočíselné násobení povoleno také jako operace na jednotku času. Rovněž byly zvažovány další specializovanější modely výpočtu, jako je paralelní stroj s náhodným přístupem , nejprve randomizované v, druhé deterministické v komentáři v; pozdější práce zahrnují

Andersson, Miltersen & Thorup (1999) ukázali, že v některých případech lze násobení nebo vyhledávání tabulek vyžadované některými algoritmy třídění celých čísel nahradit vlastními operacemi, které by byly snadněji implementovány v hardwaru, ale které nejsou obvykle k dispozici na počítačích pro všeobecné použití. Thorup (2003) to vylepšil tím, že ukázal, jak tyto speciální operace nahradit instrukcemi pro manipulaci s bitovým polem, které jsou již k dispozici u procesorů Pentium .

V externích paměťových modelech výpočetní techniky není žádný známý algoritmus třídění celých čísel rychlejší než srovnávací řazení. Výzkumníci ukázali, že v těchto modelech omezené třídy algoritmů, které jsou omezené v tom, jak manipulují s jejich klíči, nemohou být rychlejší než srovnávací třídění a že algoritmus třídění celých čísel, který je rychlejší než srovnávací řazení, by znamenal nepravdivost standardní domněnky v síťové kódování .

Třídění versus fronty s prioritou celých čísel

Prioritní fronta je datová struktura pro udržení sbírku předmětů s číselnými prioritami, které mají operace pro nalezení a odstranění položky s hodnotou minimální priority. Porovnávací prioritní fronty, jako je binární halda, vyžadují logaritmický čas na aktualizaci, ale jiné struktury, jako je strom Van Emde Boas nebo fronta kbelíku, mohou být rychlejší pro vstupy, jejichž priority jsou malá celá čísla. Tyto datové struktury lze použít v algoritmu řazení řazení , který třídí kolekci prvků opakovaným vyhledáváním a odebíráním nejmenšího prvku z kolekce a vrácením prvků v pořadí, v jakém byly nalezeny. K udržení kolekce prvků v tomto algoritmu lze použít frontu priorit a čas pro tento algoritmus na kolekci $n$ prvků lze ohraničit časem pro inicializaci fronty priorit a poté pro provedení $n$ operací hledání a odebrání. Například použití binární hromady jako prioritní fronty při řazení výběru vede k algoritmu haldy, algoritmu srovnávacího řazení, který zabere čas $O (n log n)$ . Místo toho použití výběrového třídění pomocí fronty kbelíku poskytuje formu řazení holubí díry a použití stromů van Emde Boas nebo jiných celých prioritních front vede k dalším algoritmům rychlého třídění celých čísel.

Namísto použití fronty s celočíselnou prioritou v algoritmu řazení je možné jít jiným směrem a použít algoritmy řazení celých čísel jako podprogramy v datové struktuře fronty s celočíselnou prioritou. Thorup (2007) použil tento nápad, aby ukázal, že pokud je možné provádět celočíselné třídění v čase $T (n)$ na klíč, pak stejná časová hranice platí pro čas na operaci vložení nebo odstranění v datové struktuře prioritní fronty. Thorupova redukce je komplikovaná a předpokládá dostupnost rychlých multiplikačních operací nebo vyhledávání tabulek, ale také poskytuje alternativní frontu priorit využívající pouze sčítání a booleovské operace s časem $T (n) + T (log n) + T (log log n) + ...$ za operaci, maximálně vynásobením času iterovaným logaritmem .

Použitelnost

Široce používané a praktické jsou klasické algoritmy pro třídění celých čísel při třídění holubů , počítání a radix . Velká část následného výzkumu algoritmů třídění celých čísel se zaměřila méně na praktičnost a více na teoretická vylepšení jejich analýzy nejhorších případů a algoritmy, které pocházejí z této linie výzkumu, nejsou považovány za praktické pro současné 64bitové počítačové architektury, přestože experimenty ukázaly, že některé z těchto metod mohou být vylepšení radixového třídění pro data se 128 a více bity na klíč. Navíc pro velké soubory dat mohou přístupy téměř náhodných přístupů do paměti mnoha algoritmů pro třídění celých čísel je znevýhodňovat ve srovnání s algoritmy pro srovnávací řazení, které byly navrženy s ohledem na hierarchii paměti.

Třídění celých čísel poskytuje jeden ze šesti benchmarků v sadě benchmarků DARPA High Productivity Computing Systems Discrete Mathematics a jeden z jedenácti benchmarků v sadě NAS Parallel Benchmarks .

Praktické algoritmy

Třídění Pigeonhole nebo počítání může třídit $n$ datových položek s klíči v rozsahu od $0$ do $K - 1$ v čase $O (n + K)$ . Při řazení typu pigeonhole (často nazývaném bucket sort) jsou ukazatele na datové položky distribuovány do tabulky kbelíků, reprezentované jako datové typy kolekce, jako jsou propojené seznamy , pomocí klíčů jako indexů do tabulky. Potom jsou všechny segmenty spojeny dohromady a vytvoří se výstupní seznam. Třídění počítání používá tabulku čítačů místo tabulky kbelíků k určení počtu položek s každým klíčem. Potom se pomocí výpočtu součtu prefixu určí rozsah pozic v seřazeném výstupu, na které by měly být umístěny hodnoty s každým klíčem. Nakonec ve druhém průchodu přes vstup je každá položka přesunuta na pozici svého klíče ve výstupním poli. Oba algoritmy zahrnují pouze jednoduché smyčky nad vstupními daty (zabírající čas $O (n)$ ) a nad množinou možných klíčů (zabírající čas $O (K)$ ), přičemž jejich celkový časový limit je $O (n + K)$ .

Radix sort je třídící algoritmus, který funguje pro větší klíče než pro řazení typu pigeonhole nebo pro počítání tím, že provádí více průchodů přes data. Každý průchod třídí vstup pomocí pouze části klíčů pomocí jiného třídicího algoritmu (například třídění podle holubů nebo počítání), který je vhodný pouze pro malé klíče. Aby se klíče rozdělily na části, algoritmus radixového řazení vypočítá poziční zápis pro každý klíč podle zvoleného radixu ; část klíče použitá pro $i$ -tý průchod algoritmu je $i$ -tou číslicí v pozičním zápisu pro plný klíč, počínaje od nejméně významné číslice a postupující k nejvýznamnějšímu. Aby tento algoritmus fungoval správně, musí být třídicí algoritmus použitý v každém průchodu přes data stabilní : položky se stejnými číslicemi by neměly navzájem měnit pozice. Pro maximální účinnost by měl být radix zvolen tak, aby se blížil počtu datových položek, $n$ . Navíc, s použitím síly dva blízké $n$ jako soustave umožňuje klíče na každém průchodu má být vypočítána rychle pomocí pouze rychlý binární posun a masku operace. S těmito možnostmi as řadením nebo počítáním typu pigeonhole jako základním algoritmem může řadicí algoritmus radix třídit $n$ datových položek s klíči v rozsahu od $0$ do $K - 1$ v čase $O (n log n K)$ .

Teoretické algoritmy

Bylo vyvinuto mnoho algoritmů třídění celých čísel, jejichž teoretická analýza ukazuje, že se chovají lépe než srovnávací třídění, třídění holubů nebo radixové řazení pro dostatečně velké kombinace parametrů definujících počet položek, které mají být tříděny, rozsah klíčů a velikost strojového slova. Který algoritmus má nejlepší výkon, závisí na hodnotách těchto parametrů. Navzdory svým teoretickým výhodám nejsou tyto algoritmy vylepšením typických rozsahů těchto parametrů, které vznikají při praktických problémech s tříděním.

Algoritmy pro malé klíče

Van Emde Boas strom může být použit jako prioritní fronta třídit sadu $n$ klíčů, z nichž každý v rozsahu od $0$ do $K - 1$ , v čase $O (n log log K)$ . Toto je teoretické zlepšení oproti radixovému třídění, když je $K$ dostatečně velký. Abychom však mohli použít strom Van Emde Boas, buď potřebujeme přímo adresovatelnou paměť $K$ slov, nebo ji musíme simulovat pomocí hashovací tabulky , zmenšením prostoru na lineární, ale tím, že algoritmus bude randomizován. Další prioritní fronta s podobným výkonem (včetně potřeby randomizace ve formě tabulek hash) je Y-rychlý trie of Willard (1983) .

Sofistikovanější techniku s podobnou chutí as lepším teoretickým výkonem vyvinula společnost Kirkpatrick & Reisch (1984) . Pozorovali, že každý průchod radixového řazení lze interpretovat jako techniku redukce rozsahu, která v lineárním čase zmenšuje maximální velikost klíče o faktor $n$ ; místo toho jejich technika zmenšuje velikost klíče na druhou odmocninu jeho předchozí hodnoty (snížení počtu bitů potřebných k reprezentaci klíče na polovinu), opět v lineárním čase. Stejně jako v soustave druhu, oni interpretovat klíče jako dvoumístná Základní- $b$ čísel pro základní $b$ , která je přibližně $\sqrt K$ . Poté seskupí položky, které mají být tříděny do kbelíků podle jejich vysokých číslic, v lineárním čase, buď pomocí velké, ale neinicializované přímé adresované paměti, nebo hashovací tabulky. Každý kbelík má svého zástupce, předmět v kbelíku s největším klíčem; poté seřadí seznam položek pomocí klíčů vysokých číslic zástupců a nízkých číslic zástupců. Opětovným seskupením položek z tohoto seznamu do segmentů lze každý segment umístit do seřazeného pořadí a extrahováním zástupců z seřazeného seznamu lze segmenty spojit dohromady do seřazeného pořadí. V lineárním čase se tedy problém třídění redukuje na další problém rekurzivního třídění, ve kterém jsou klíče mnohem menší, druhá odmocnina jejich předchozí velikosti. Opakování tohoto snižování rozsahu, dokud nejsou klíče dostatečně malé na to, aby vedlo třídění, vede k algoritmu s dobou běhu $O (n log log n K)$ .

Komplikovaný randomizovaný algoritmus Han & Thorup (2002) v modelu výpočtu slova RAM umožňuje tyto časové limity snížit ještě dále na $O ($ $n$ $\sqrt$ $log log$ $K$ $)$ .

Algoritmy pro velká slova

Algoritmus třídění celých čísel je považován za nekonzervativní, pokud vyžaduje velikost slova $w,$ která je výrazně větší než $log max (n, K)$ . V extrémním případě, pokud $w \geq K$ a všechny klíče jsou odlišné, pak lze sadu klíčů řadit v lineárním čase tak, že ji představíme jako bitvektor , přičemž 1 bit v poloze $i,$ když $i$ je jedním ze vstupních klíčů, a poté opakovaně odebírat nejméně významný bit.

Non-konzervativní zabalené třídění algoritmus Albers & Hagerup (1997) používá podprogram, založený na Ken Dávkovače ‚s bitonic třídicí sítě pro sloučení dvou řazeny sekvence kláves, které jsou každá krátká dost být zabaleno do jediného slova stroje. Vstup do zabaleného třídicího algoritmu, posloupnost položek uložených po jednom na slovo, se transformuje do zabalené podoby, posloupnosti slov, z nichž každá obsahuje více položek v seřazeném pořadí, pomocí tohoto podprogramu opakovaně zdvojnásobí počet položek zabalených do každého slovo. Jakmile je sekvence v zabalené formě, Albers a Hagerup použijí k jejímu třídění formu sloučení ; když jsou dvě sekvence sloučeny do jedné delší sekvence, může být stejný podprogram bitonického třídění použit k opakovanému extrahování zabalených slov sestávajících z nejmenších zbývajících prvků těchto dvou sekvencí. Tento algoritmus získává ze své zabalené reprezentace dostatečné zrychlení, aby třídil svůj vstup v lineárním čase, kdykoli je možné, aby jedno slovo obsahovalo klíče $Ω (log n log log n)$ ; to znamená, že když $log K log n log log n \leq cw$ pro nějakou konstantu $c > 0$ .

Algoritmy pro několik položek

Třídění Pigeonhole, počítání, radix a třídění stromů Van Emde Boas funguje nejlépe, když je velikost klíče malá; u dostatečně velkých klíčů se stanou pomalejšími než algoritmy srovnávacího řazení. Když je však velikost klíče nebo velikost slova velmi velká vzhledem k počtu položek (nebo ekvivalentně, když je počet položek malý), může být opět možné rychle řadit pomocí různých algoritmů, které využívají výhody paralelismu ve schopnosti provádět aritmetické operace s velkými slovy.

Časný výsledek v tomto směru poskytli Ajtai, Fredman & Komlós (1984) pomocí modelu výpočtu buňka-sonda (umělý model, ve kterém je složitost algoritmu měřena pouze počtem přístupů do paměti, které provádí). Na základě své práce Fredman & Willard (1994) popsal dvě datové struktury, haldu Q a atomovou hromadu, které jsou implementovatelné na stroji s náhodným přístupem. Halda Q je bitově paralelní verze binárního triu a umožňuje provádět operace prioritních front i dotazy nástupců a předchůdců v konstantním čase pro sady položek $O ((log N) 1/4)$ , kde $N \leq 2 w$ je velikost předpočtených tabulek potřebných k implementaci datové struktury. Atomová hromada je strom B, ve kterém je každý uzel stromu reprezentován jako hromada Q; umožňuje operace fronty s konstantní časovou prioritou (a tedy řazení) pro sady $(log N) O (1)$ položek.

Andersson a kol. (1998) poskytují randomizovaný algoritmus nazývaný podpisové řazení, které umožňuje lineární časové třídění sad až $2$ položek $O$ $((log$ $w$ $)$ $1/2 - ε$ $)$ najednou pro libovolnou konstantu $ε> 0$ . Stejně jako v algoritmu Kirkpatricka a Reische provádějí redukci dosahu pomocí reprezentace klíčů jako čísel v základně $b$ pro pečlivý výběr $b$ . Jejich algoritmus redukce rozsahu nahradí každou číslici podpisem, což je hašovaná hodnota s bity $O (log n)$ , takže různé číselné hodnoty mají různé podpisy. Pokud je $n$ dostatečně malé, budou čísla vytvořená tímto náhradním procesem výrazně menší než původní klíče, což umožní nekonzervativnímu algoritmu seřazeného řazení Albers & Hagerup (1997) třídit nahrazená čísla v lineárním čase. Z seřazeného seznamu nahrazených čísel je možné vytvořit komprimovaný trius klíčů v lineárním čase a potomky každého uzlu v triu lze rekurzivně třídit pouze pomocí klíčů velikosti $b$ , načež stromový traverz vytvoří seřazené pořadí položek.

Transdichotomické algoritmy

Fredman & Willard (1993) představili transdichotomický model analýzy pro algoritmy třídění celých čísel, ve kterém se nepředpokládá nic o rozsahu celých klíčů a výkon algoritmu musí být vázán funkcí samotného počtu datových hodnot. Alternativně je v tomto modelu doba běhu pro algoritmus na sadě $n$ položek považována za nejhorší případ doby běhu pro jakoukoli možnou kombinaci hodnot $K$ a $w$ . Prvním algoritmem tohoto typu byl algoritmus třídění fúzního stromu Fredmana a Willarda , který běží v čase $O (n log n / log log n)$ ; toto je vylepšení oproti srovnávacímu řazení pro jakýkoli výběr $K$ a $w$ . Alternativní verze jejich algoritmu, která zahrnuje použití náhodných čísel a operací dělení celých čísel, to vylepšuje na $O (n \sqrt log n)$ .

Od jejich práce byly vyvinuty ještě lepší algoritmy. Například opakovaným aplikováním techniky redukce dosahu Kirkpatrick – Reisch, dokud nejsou klíče dostatečně malé pro použití Albers – Hagerupova baleného třídicího algoritmu, je možné řadit v čase $O (n log log n)$ ; část redukce dosahu tohoto algoritmu však vyžaduje buď velkou paměť (úměrnou $\sqrt K$ ), nebo randomizaci ve formě hashovacích tabulek.

Han & Thorup (2002) ukázal, jak třídit v náhodném čase $O (n \sqrt log log n)$ . Jejich technika zahrnuje použití nápadů souvisejících s tříděním podpisů k rozdělení dat do mnoha malých podseznamů o velikosti dostatečně malé, aby řazení podpisů dokázalo efektivně řadit každý z nich. Je také možné použít podobné nápady k třídění celých čísel deterministicky v čase $O (n log log n)$ a lineárním prostoru. Pomocí pouze jednoduchých aritmetických operací (bez násobení nebo vyhledávání v tabulce) je možné řadit v náhodném očekávaném čase $O (n log log n)$ nebo deterministicky v čase $O (n (log log n) 1 + ε)$ pro libovolnou konstantu $ε> 0$ .

Reference

Poznámky pod čarou

Sekundární zdroje

Chowdhury, Rezaul A. (2008), „Ekvivalence mezi prioritními frontami a tříděním“ , in Kao, Ming-Yang (ed.), Encyclopedia of Algorithms , Springer, s. 278–281, ISBN 9780387307701.
Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001), Úvod do algoritmů (2. vydání), MIT Press a 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ární zdroje

Aggarwal, Alok; Vitter, Jeffrey S. (září 1988), „Vstupní/výstupní složitost řazení a související problémy“, Communications of the ACM , 31 (9): 1116–1127, doi : 10.1145/48529.48535
Ajtai, M .; Fredman, M .; Komlós, J. (1984), „Hash funkce pro prioritní fronty“, Information and Control , 63 (3): 217–225, doi : 10,1016/S0019-9958 (84) 80015-7 , MR 0837087.
Albers, Susanne ; Hagerup, Torben (1997), „Vylepšené třídění paralelních celých čísel bez souběžného psaní“, Information and Computation , 136 (1): 25–51 , CiteSeerX 10.1.1.53.498 , doi : 10.1006/inco.1997.2632 , MR 1457693.
Andersson, Arne; Hagerup, Torben; Nilsson, Stefan; Raman, Rajeev (1998), „Třídění v lineárním čase?“, 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 , MR 1717389.
Andersson, Arne; Miltersen, Peter Bro; Thorup, Mikkel (1999), „Fusion stromy lze implementovat pouze podle pokynů $AC 0$ “, Theoretical Computer Science , 215 (1–2): 337–344 , CiteSeerX 10.1.1.32.9401 , doi : 10.1016/S0304-3975 ( 98) 00172-8 , MR 1678804.
Bhatt, PCP; Diks, K .; Hagerup, T .; Prasad, VC; Radzik, T .; Saxena, S. (1991), „Improved deterministic parallel integer sorting“, Information and Computation , 94 (1): 29–47, doi : 10.1016/0890-5401 (91) 90031-V , MR 1123154.
Cole, R .; Vishkin, U. (1986), „Deterministické ražení mincí s aplikacemi k optimálnímu souběžnému hodnocení seznamu“, Information and Control , 70 (1): 32–53, doi : 10.1016/S0019-9958 (86) 80023-7.
Comrie, LJ (1929–1930), „Tabulační stroje Hollerith a Powers“, přel. Kancelář Mach. Assoc. Uživatelů, LTD. : 25–37. Citován Thorupem (2007) jako raný zdroj pro radixové řazení .
Farhadi, Alireza; Hajiaghayi, Mohammad Taghi ; Larsen, Kasper Green; Shi, Elaine (září 2020), „Dolní hranice pro třídění celých čísel v externí paměti prostřednictvím síťového kódování“, komunikace ACM , 63 (10): 97–105, arXiv : 1811.01313 , doi : 10.1145/3416268.
Fredman, Michael L .; Willard, Dan E. (1993), „Překračování informačně teoretické vazby s fúzními stromy“, 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-dichotomické algoritmy pro minimální překlenovací stromy a nejkratší cesty“, Journal of Computer and System Sciences , 48 (3): 533–551, doi : 10,1016/S0022-0000 (05) 80064 -9 , MR 1279413.
Hagerup, Torben (1987), „Směrem k optimálnímu paralelnímu třídění kbelíku“, Information and Computation , 75 (1): 39–51, doi : 10.1016/0890-5401 (87) 90062-9 , MR 0910976.
Han, Yijie (2004), „Deterministické třídění v $O (n log log n)$ čase a lineárním prostoru“, Journal of Algorithms , 50 (1): 96–105, doi : 10,1016/j.jalgor.2003.09.001 , MR 2028585.
Han, Yijie; Thorup, M. (2002), „Celočíselné třídění v $O (n \sqrt log log n)$ očekávaný čas a lineární prostor“, sborník ze 43. výročního sympozia o základech informatiky (FOCS 2002) , IEEE Computer Society, s. 135 –144, doi : 10,1109/SFCS.2002.1181890.
Kirkpatrick, David ; Reisch, Stefan (1984), „Horní hranice pro třídění celých čísel na strojích s náhodným přístupem“, 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), Studie praktického významu algoritmů slovní RAM pro interní třídění celých čísel , Magisterská práce, Katedra informatiky, Univerzita v Kodani, Dánsko, archivováno z originálu dne 2012-03-16 , vyvoláno 2011 -04-21.
Rahman, Naila; Raman, Rajeev (1998), „Experimentální studie paralelizmu na úrovni slov v některých algoritmech třídění“, Algorithm Engineering, 2. mezinárodní workshop, WAE '92, Saarbrücken, Německo, 20. – 22. Srpna 1998, sborník (PDF) , Max Planck Institute for Computer Science , s. 193–203.
Reif, John H. (1985), „Optimální paralelní algoritmus pro třídění celých čísel“, Proceedings of the 26th Annual Symposium on Foundations of Computer Science (FOCS 1985) , IEEE Computer Society, pp. 496–504, doi : 10.1109/SFCS 0,1985,9.
Thorup, Mikkel (2002), „Randomized sorting in $O (n log log n)$ time and linear space using adds, shift, and bit-múdry Boolean operations“, Journal of Algorithms , 42 (2): 205–230, CiteSeerX 10.1 .1.55.4443 , doi : 10.1006/jagm.2002.1211 , MR 1895974.
Thorup, Mikkel (2003), „O implementacích fúzních stromů a atomových hromad $AC 0$ “, sborník ze čtrnáctého výročního sympozia ACM-SIAM o diskrétních algoritmech (Baltimore, MD, 2003) , New York: ACM, s. 699–707 , MR 1974982.
Thorup, Mikkel (2007), „Ekvivalence mezi prioritními frontami a tříděním“, Journal of the ACM , 54 (6): Art. 28, doi : 10,1145/1314690.1314692 , MR 2374029.
Willard, Dan E. (1983), „Log-logaritmické dotazy na rozsah nejhorších případů jsou možné v prostoru $Θ (N)$ “, Information Processing Letters , 17 (2): 81–84, doi : 10,1016/0020-0190 (83 ) 90075-3 , MR 0731126.

Languages

In other projects