Redigerer Kvikksortering (avsnitt)

====Parallellisering====
Quicksorts splitt og hersk-formulering gjør den egnet for [[parallell algoritme|parallellisering]] ved å bruke [[oppgaveparallellisme]]. Partisjoneringstrinnet blir oppnådd gjennom bruken av en [[prefixsum|parallell prefixsum]]-algoritme for å beregne en indeks for hvert tabellelement i sin seksjon av den partisjonerte tabellen.<ref name="Acar2013"/><ref name="Breshears2012"/> Dersom vi har en tabell av størrelse {{mono|'''{{math|''n''}}'''}}, utfører partisjoneringstrinnet et arbeid på {{mono|'''{{math|O(''n'')}}'''}} i tidsrommet {{mono|'''{{math|''O''(log ''n'')}}'''}} som krever {{mono|'''{{math|O(''n'')}}'''}} tilleggsplass. Etter at tabellen har blitt partisjonert, kan de to partisjonene bli sortert rekursivt i parallell. Ved å anta et ideelt valg for «dreiepinner», sorterer parallell quicksort en tabell av størrelse {{mono|'''{{math|''n''}}'''}} med et arbeid på {{mono|'''{{math|O(''n'' log ''n'')}}'''}} i tidsrommet {{mono|'''{{math|O(log² ''n'')}}'''}} ved å bruke {{mono|'''{{math|O(''n'')}}'''}} tilleggsplass.

Quicksort har enkelte ulemper sammenlignet med andre sorteringsalgoritmer, eksempelvis [[flettesortering]], som kompliserer dets effektive parallellisering. Dybden av quicksort's splitt-og-hersk tre påvirker direkte algortimens skalerbarhet, og denne dybden er svært avhengig av algoritmens «dreiepinne». I tillegg er det vanskelig å parallellisere partisjoneringstrinnet på-stedet. Bruken av tilleggs-lagringsplass forenkler partisjoneringstrinnet, men øker algortimens bruk av minne og gir konstante [[overhead (informatikk)|overhead]].

Andre mer sofistikerte parallele sorteringsalgoritmer kan oppnå dette innenfor bedre tidsgrenser.<ref name="Miller2000"/> I 1991 beskrev for eksempel David Powers en parallellisert quicksort (og en beslektet [[radixsortering]]) som kan operere med en tid på {{mono|'''{{math|''O''(log ''n'')}}'''}} på en CRCW [[Parallel random access-machine|PRAM]] (''parallel random-access machine'') med ''n'' [[mikroprosessor]]er som utfører partisjonering implisitt.<ref name="Powers1991"/>