Redigerer Kvikksortering (avsnitt)

==Algoritme==
[[Fil:Quicksort-diagram.svg|right|200px|thumb|Eksempel på Lomutos variant av quicksort på en tilfeldig mengde tall. De gråe elementer er «dreietappen», og blir alltid valgt som siste element i partisjonen. Versjoner av quicksort som velger «dreietappen» som midterste element kjører mye raskere enn Lomutos metode.]]
Quicksort er en «[[splitt-og-hersk-algoritme]]». Algoritmen deler først en tabell (eller liste) opp i to mindre undertabeller (eller underlister), som inneholder de laveste elementer og høyere elementer. Deretter blir undertabellene sortert [[rekursjon|rekursivt]].

Trinnene i algoritmen er:

* Plukk et element, kalt «dreietapp» (''pivot''), fra tabellen
* Partisjoner tabellen slik at alle elementer med lavere verdi enn «dreietappen» går forut for denne, mens verdier som er større kommer etter denne (like verdier kan gå i hver retning). Etter partisjoneringen er «dreietappen» i sin endelige posisjon. Dette kalles partisjons-operasjonen.
* Anvend trinnene ovenfor rekursivt på undertabellene med mindre elementer og deretter separat på undertabellene med større elementer

Det enkleste tilfelle av rekursjon er tabeller av størrelse 0 eller 1, som aldri trenger å sorteres.

Valg av «dreietapp» og partisjonering kan gjøres på flere måter, og valget av implementasjonsmetode har stor påvirkning på algoritmens ytelse.

===Lomutos metode===
Denne metoden tilegnes Nico Lomuto og ble popularisert av Bentley i boken ''Programming Pearls'',<ref name="Bentley1999"/> og av [[Thomas H. Cormen]] med flere i boken ''Introduction to Algorithms''.<ref name="Cormen2009"/> Metoden velger en «dreiepinne» som vanligvis er siste element i tabellen. Algoritmen ivaretar indeksen til «dreiepinnen» i variabelen ''i'', og hver gang den finner et element som er mindre enn eller likt «dreiepinnen» blir denne indeksen inkrementert og dette elementet plasseres foran «dreiepinnen». Denne metoden er mer kompakt og lettere å forstå og er ofte brukt i introduksjoner av algoritmer, men er mindre effektiv enn Hoares opprinnelige metode.<ref name="Wild2012"/> I verste tilfelle krever denne metoden {{math|''O''(''n''<sup>2</sup>)}} sammenligninger. Det skjer når tabellen allerede er sortert eller når den bare har identiske elementer.<ref name="CS2017"/> Ulike varianter av metoden har blitt foreslått for å øke ytelsen, deriblant ulike måter å velge «dreiepinne», håndtering av identiske elementer, bruk av andre algoritmer som f.eks. innstikksortering for mindre tabeller, etc. I [[pseudokode]] kan en quicksort som sorterer elementer fra {{mono|lo}} til {{mono|hi}} i en tabell ''A'' bli uttrykt på følgende måte:<ref name="Cormen2009_170-190"/>

 '''algoritme''' quicksort(A, lo, hi) '''er'''
     '''if''' lo < hi '''then'''
         p := partition(A, lo, hi)
         quicksort(A, lo, p – 1)
         quicksort(A, p + 1, hi)
 
 '''algoritme''' partition(A, lo, hi) '''er'''
     dreietapp := A[hi]
     i := lo     ''// sted for ombytting''
     '''for''' j := lo '''to''' hi – 1 '''do'''
         '''if''' A[j] ≤ dreietapp '''then'''
             bytt om A[i] og A[j]
             i := i + 1
     bytt om A[i] og A[hi]
     '''return''' i

Å sortere hele tabellen blir oppnådd gjennom rutinekallet {{mono|quicksort(A, 1, lengde(A))}}.

===Hoares metode===
[[Fil:Lomuto animated.gif|thumb|300px|Animasjon av Lomuto's metode]]
[[Fil:Quicksort-example.gif|thumb|300px|Animasjon av Hoare's metode]]
Den opprinnelige metoden som er beskrevet av C.A.R. Hoare, bruker to indekser som begynner på begge endene av tabellen som partisjoneres, og som deretter beveger seg mot hverandre, inntil de oppdager en inversjon: Et par av elementer, det ene større enn eller identisk med «dreietappen» og det andre mindre eller identisk, som er i feil rekkefølge relativt til hverandre. De inverterte elementene blir deretter byttet om med hverandre.<ref name="Hoare1962"/> Når indeksene møtes, vil algoritmen stoppe og returnere den endelige indeks. Det finnes mange varianter av denne algoritmen, deriblant å velge «dreietapp» fra {{mono|A[hi]}} i stedet for {{mono|A[lo]}}. Hoare's metode er mer effektiv enn Lomuto's fordi den foretar tre færre ombyttinger i gjennomsnitt, og fordi den skaper effektive partisjoneringer selv når alle verdier er identiske.<ref name="CS2017"/> Hoares partisjonering vil, liksom Lomuto's metode, kreve {{math|''O''(''n''<sup>2</sup>)}} når den innmatede tabellen allerede er sortert. På samme måte produserer den ikke en stabil sortering. «Dreietappens» endelige lokalisering er ikke nødvendigvis ved indeksen som ble returnert, og de neste to segmenter som hovedalgoritmen frembringer er {{mono|(lo..p)}} og {{mono|(p+1..hi)}} i stedet for {{mono|(lo..p-1)}} og {{mono|(p+1..hi)}} som tilfellet er i Lomuto's metode. I pseudokode blir Hoares metode slik:<ref name="Cormen2009_170-190"/>

 '''algoritme''' quicksort(A, lo, hi) '''er'''
     '''if''' lo < hi '''then'''
         p := partition(A, lo, hi)
         quicksort(A, lo, p)
         quicksort(A, p + 1, hi)
 
 '''algoritme''' partition(A, lo, hi) '''er'''
     dreietapp := A[lo]
     i := lo - 1
     j := hi + 1
     '''loop forever'''
         '''do'''
             i := i + 1
         '''while''' A[i] < dreietapp
 
         '''do'''
             j := j - 1
         '''while''' A[j] > dreietapp
 
         '''if''' i >= j '''then'''
             '''return''' j
 
         bytt om A[i] og A[j]

===Jaroslavskijs metode===
Jaroslavskijs metode benytter to «dreietapper».<ref name="Jaroslavskij2009"/> Den partisjonerer den usorterte tabellen {{mono|'''T [] a'''}}, hvor {{mono|'''T'''}} er en primitiv type ([[heltall]], [[flyttall]], [[byte]], [[tegn]], [[dobbelpresisjons flyttallsformat|dobbel]], langt heltall og kort heltall) som defineres av to «dreietapper» {{mono|'''P1'''}} og {{mono|'''P2'''}}. Det er derfor tre pekere, {{mono|'''L'''}}, {{mono|'''K'''}}, {{mono|'''G'''}}, og to indekser, {{mono|'''left'''}} and {{mono|'''right'''}}, som peker på henholdsvis det første og det siste elementet.<ref name="Jaroslavskij2009"/> Algoritmen består av følgende trinn:<ref name="Jaroslavskij2009"/>

# For mindre tabeller (lengde < 27) bruk innstikksortering
# Velg to «dreietapper» {{mono|'''P1'''}} og {{mono|'''P2'''}}. Vi kan for eksempel, velge det første elementet {{mono|'''a[left]'''}} som {{mono|'''P1'''}} og det siste elementet {{mono|'''a[right]'''}} som {{mono|'''P2'''}}
# {{mono|'''P1'''}} må være mindre enn {{mono|'''P2'''}}. I motsatt fall må de byttes om. Det er derfor fire deler:
##del 1 som indekserer fra {{mono|'''left+1'''}} til {{mono|'''L-1'''}}, med elementer som er mindre enn {{mono|'''P1'''}}
##del 2 som indekserer fra {{mono|'''L'''}} til {{mono|'''L-1'''}}, med elementer som er større enn eller lik {{mono|'''P1'''}} og mindre enn eller lik {{mono|'''P2'''}}
##del 3 som indekserer fra {{mono|'''G+1'''}} til {{mono|'''right–1'''}} med elementer som er større enn {{mono|'''P2'''}}
##del 4 inneholder resten av indeksene fra {{mono|'''K'''}} til {{mono|'''G'''}}
#Det neste elementet ved {{mono|'''a[left]'''}} i del 4 blir sammenlignet med de to «dreiebenkene» {{mono|'''P1'''}} og {{mono|'''P2'''}}, og plasseres i den korresponderende del 1, del 2, eller del 3
#Pekerne {{mono|'''L'''}}, {{mono|'''K'''}} og {{mono|'''G'''}} forandres i de korresponderende retninger
#Trinnene 4 og 5 blir repetert så lenge {{mono|'''K ≤ G'''}}
#«Dreietappen» {{mono|'''P1'''}} blir byttet med det siste elementet fra del 1, og «dreietappen» {{mono|'''P2'''}} blir byttet med det siste elementet fra del 3
# Trinn 1-7 blir gjentatt rekursivt for hver enkelt del, del 1, del 2 og del 3

Her er koden for Jaroslavskijs metode, skrevet i programmeringsspråket Java:<ref name="Jaroslavskij2009"/>

<syntaxhighlight lang="C">
  public static void sort(int[] a) {
     sort(a, 0, a.length);
  }

  public static void sort(int[] a, int fromIndex, int toIndex) {
     rangeCheck(a.length, fromIndex, toIndex);
     dualPivotQuicksort(a, fromIndex, toIndex - 1, 3);
  }

  private static void rangeCheck(int length, int fromIndex, int toIndex) {
    if (fromIndex > toIndex) {
       throw new IllegalArgumentException("fromIndex > toIndex");
    }
    if (fromIndex < 0) {
       throw new ArrayIndexOutOfBoundsException(fromIndex);
    }
    if (toIndex > length) {
       throw new ArrayIndexOutOfBoundsException(toIndex);
    }
  }

  private static void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
  }

  private static void dualPivotQuicksort(int[] a, int left,int right, int div) {
    int len = right - left; 
    if (len < 27) { // insertion sort for tiny array
      for (int i = left + 1; i <= right; i++) {
        for (int j = i; j > left && a[j] < a[j - 1]; j--) {
          swap(a, j, j - 1);
        }
      }
    return;
    }
    int third = len / div;
    // «medianer»
    int m1 = left + third;
    int m2 = right - third;

    if (m1 <= left) {
       m1 = left + 1;
    }
    if (m2 >= right) {
       m2 = right - 1;
    }
    if (a[m1] < a[m2]) {
      swap(a, m1, left);
      swap(a, m2, right);
    } else {
     swap(a, m1, right);
     swap(a, m2, left);
    }

    // dreietapper
    int pivot1 = a[left];
    int pivot2 = a[right];

    // pekere
    int less = left + 1;
    int great = right - 1;

  // sortering
    for (int k = less; k <= great; k++) {
       if (a[k] < pivot1) {
       swap(a, k, less++);
    }
    else if (a[k] > pivot2) {
       while (k < great && a[great] > pivot2) {
       great--;
       }
       swap(a, k, great--);
       if (a[k] < pivot1) {
          swap(a, k, less++);
       }
    }
  }
  // ombyttinger
  int dist = great - less;

  if (dist < 13) {
     div++;
  }
  swap(a, less - 1, left);
  swap(a, great + 1, right);
  // undertabeller
  dualPivotQuicksort(a, left, less - 2, div);
  dualPivotQuicksort(a, great + 2, right, div);
  // like elementer
     if (dist > len - 13 && pivot1 != pivot2) {
        for (int k = less; k <= great; k++) {
        if (a[k] == pivot1) {
          swap(a, k, less++);
        } else if (a[k] == pivot2) {
            swap(a, k, great--);
        if (a[k] == pivot1) {
           swap(a, k, less++);
        }
      }
    }
  }
  // undertabeller
  if (pivot1 < pivot2) {
    dualPivotQuicksort(a, less, great, div);
  }
  }
</syntaxhighlight>

===Ulike former for implementasjon===
====Valg av «dreietapp»====
I de aller første tidlige versjonene av quicksort, kunne elementet til venstre av partisjonen ofte bli valgt som «dreietapp». Uheldigvis, forårsaker dette en adferd av det verste tilfelle på tabeller som allerede er sortert, noe som er et vanlig tilfelle. Dette problemet ble lett løst ved å enten velge en tilfeldig indeks for «dreietappen», enten i form av den midterste indeksen i partisjonen eller (særlig for lange partisjoner) medianen av det første, midterste og siste elementet av partisjonen. Denne løsningen ble foreslått av Robert Sedgewick.<ref name="Sedgewick1998"/><ref name="Sedgewick1978"/> Denne «medianen-av-tre» regelen teller tilfeller av sortert (eller det omvendte av sortert) innmatning, og gir et bedre estimat på den optimale «dreietapp» (den sanne median) enn å velge et hvilket som helst enkeltelement når ingen informasjon om rekkefølgen er tilstede.

Det forventede antallet sammenligninger som er nødvendig for å sortere {{math|''n''}} er

:{{mono|'''{{math|''n''}} = {{math|1.386 ''n'' log ''n''}}'''}}.

«Medianen-av-tre» regelen bringer dette ned i 

: {{mono|'''{{math|''C''<sub>''n'', 2</sub> ≈ 1.188 ''n'' log ''n''}}'''}}

(der {{mono|'''C'''}} er [[binomialkoeffisient]]en) på bekostninga av en forventet økning av bytter.<ref name="Bentley1993"/> En mer kraftig regel for valg av «dreietapp», for større tabeller, er å velge ''ninther'', en rekursiv «median-av-tre» (Mo3), definert som:<ref name="Bentley1993"/>

:{{mono|'''{{math|ninther(''a'') {{=}} median (Mo3(første ⅓ av ''a''), Mo3(midterste ⅓ av ''a''), Mo3(siste ⅓ av ''a''))}}'''}}

Valg av «dreietapp» kompliseres også av eksistensen av [[heltallsoverflyt]]. Dersom grenseindeksene for undertabellen som blir sortert er tilstrekkelig store, vil det enkle uttrykk for middelindeksen {{math|(''lo'' + ''hi'')/2}} forårsake overflyt og gi en feilaktig «dreietapp»-indeks. Dette kan bli unngått ved å bruke, for eksempel, {{math|''lo'' + (''hi''−''lo'')/2}} til å indeksere det midterste elementet, på bekostning av en mer kompleks [[aritmetikk]]. Lignende problemstillinger oppstår i en del andre metoder for valg av «dreietapp».

====Repeterte elementer====
For partisjonsalgoritmer slik som de som er beskrevet ovenfor (også de som velger gode «dreietapp»-verdier), fremviser quicksort en dårlig ytelse hvis tabellen inneholder mange repeterende elementer. Problemet er tydelig når alle elementer i tabellen er like: I hver rekursjon er venstre partisjon tom (ingen verdi er mindre enn «dreietappen»), og høyre partisjon har bare minsket med et element («dreietappen» er fjernet). Denne algoritmen krever konsekvent [[tidskompleksitet|kvadratisk tid]] for å sortere en tabell med like verdier.

For å løse dette problemet, som noen ganger blir kalt «[[det nederlandske flaggets problem]]»,<ref name="Bentley1993"/> kan en alternativ partisjonsrutine som bruker lineær tid bli brukt for å dele verdiene opp i tre grupper: Verdier mindre enn «dreietappen», verdier like store som «dreietappen» og verdier større enn «dreietappen». Jon Bentley og Douglas McIlroy har kalt dette en «feit partisjon» og har bemerket at den allerede ble implementert i {{mono|[[qsort]]}} i [[UNIX versjon 7]] (1979).<ref name="Bentley1993"/> Verdiene som er identisk med «dreietappen» er allerede sortert, slik at bare partisjoner som er mindre enn og større enn «dreietappen» krever en rekursiv sortering. I pseudokode blir quicksort-algoritmen slik:

 '''algoritme''' quicksort(A, lo, hi) '''er'''
     '''if''' lo < hi '''then'''
         p := pivot(A, lo, hi)
         left, right := partition(A, p, lo, hi)  ''// Flere returverdier''
         quicksort(A, lo, left)
         quicksort(A, right, hi)

Det beste tilfelle for algortitmen inntreffer nå når alle elementer er identiske, eller blir valgt fra en liten mengde av {{mono|'''{{math|''k'' ≪ ''n''}}'''}} elementer. I tilfeller med bare identiske elementer, vil den modifiserte quicksort utføre på det meste to rekursive kall på tomme undertabeller og således avsluttes i lineær tid.

====Optimaliseringer====
To andre viktige optimaliseringer, ble foreslått av Sedgewick, og er mye utbredt i praksis. Blant annet brukes de av [[GNU C Library]] (glibc). De består i:<ref name="GNUC2017"/>

*For å være sikker på at for det meste {{mono|'''{{math|''O''(log ''n'')}}'''}} minne blir brukt, utfører vi rekursivt den minste siden av partisjonen, og deretter foretar et kall for å utføre rekursjon på den andre.
*Når antall elementer er under en viss grense (kanskje ti elementer), svitsjer vi til en ikke-rekursiv sorteringslagoritme som utfører færre ombyttinger, sammenligninger eller andre operasjoner på såpass små tabeller
*En eldre variant av den tidligere optimalisering: Når antallet elementer er mindre enn terskelen ''k'', stopper vi kort og godt opp; etter at hele tabellen har blitt prosessert, foretar vi innstikksortering på den. Å stoppe rekursjonen tidlig etterlater tabellen ''k''-sortert, som betyr at hvert element er maksimalt ''k'' posisjoner unna sin endelige ferdigsorterte form. I dette tilfellet krever innstikksorteringen en tid på {{mono|'''{{math|''O''(''kn'')}}'''}} for å avslutte sorteringen, en tid som er lineær hvis ''k'' er en konstant.<ref name="Sedgewick1978"/><ref name="Bentley1999_117"/> Sammenlignet med mange «småsorterings»-optimaliseringer, kan denne versjonen utføre færre instruksjoner, men den gjør ikke optimal bruk av [[hurtigminne]]t i moderne datamaskiner.<ref name="LaMarca1999"/>

====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"/>

===Formell analyse===
==== Analyse av verste tilfelle ====
Den mest ubalanserte posisjon inntreffer når «dreiepinnen» deler listen opp i to underlister med størrelsene {{math|0}} og {{math|''n'' − 1}}. Dette kan inntreffe hvis «dreiepinnen» er det minste eller det største elementet i listen, eller i enkelte implementasjoner (Lomutos metode) når alle elementene er like.

Hvis dette inntreffer gjentatte ganger i hver posisjon, da prosesserer hvert rekursivt kall en liste som er en mindre i størrelse enn den forrige listen. Vi kan foreta {{mono|'''{{math|''n'' − 1}}'''}} nøstede kall før vi kommer til en liste av størrelse 1. Dette betyr at [[kallstakk]]en er en lineær kjede av {{mono|'''{{math|''n'' − 1}}'''}} nøstede kall. Kall nr ''i'' foretar {{mono|'''{{math|''O''(''n'' − ''i'')}}'''}} arbeid på partisjonen, og <math>\textstyle\sum_{i=0}^n (n-i) = O(n^2)</math>, slik at i dette tilfellet krever Quicksort et tidsforbruk på {{mono|'''{{math|''O''(''n''²)}}'''}}.

==== Analyse av beste tilfelle ====
I det mest balanserte tilfelle, deles listen inn i to nesten like store deler hver gang vi utfører en partisjonering. Dette betyr at hvert rekursive kall prosesserer en liste av halve størrelsen, Og vi kan foreta kun {{mono|'''{{math|log<sub>2</sub> ''n''}}'''}} nøstede kall før vi kommer til en liste av størrelse 1. Dette betyr at dybden av kallstakken er {{mono|'''{{math|log<sub>2</sub> ''n''}}'''}}. Men to kall på samme nivå av kallstakken prosesserer aldri den samme delen av den samme listen; hvert nivå av kall behøver derfor bare en tid på totalt {{mono|'''{{math|''O''(''n'')}}'''}}. Hvert av kallene har en viss konstant overhead, men ettersom det bare er {{mono|'''{{math|''O''(''n'')}}'''}} kall på hvert nivå, er dette tatt hensyn til i faktoren {{mono|'''{{math|''O''(''n'')}}'''}}. Resultatet er at algoritmen bare bruker en tid på {{mono|'''{{math|''O''(''n'' log ''n'')}}'''}}.

==== Analyse av gjennomsnittlig tilfelle ====
For å sortere en liste på ''n'' distinkte elementer, krever quicksort en forventet tid på {{mono|'''{{math|''O''(''n'' log ''n'')}}'''}}, i gjennomanitt på alle {{mono|'''{{math|''n''!}}'''}} [[permutasjon]]er av ''n'' elementer [[diskret uniform distribusjon|lik sannsynlighet]]. Vi oppgir her tre vanlige bevis på at denne påstanden gir oss forskjellig innsikt i quicksort's virkemåte.

===== Bruk av persentiler =====
Hvis hver «dreiepinne» har en rangering i de midterste 50%, det vil si mellom den 25. [[persentil]] og den 75. persentil, da sålitter den elementer med minimum 25% og maksimum 75% på hver side. Dersom vi konsekvent kunne velge slike «dreiepinner», da ville vi bare måtte splitte listen maksimum  {{mono|'''<math>\log_{4/3} n</Math>'''}} ganger før vi fikk lister av størrelse 1, noe som ville medføre en {{mono|'''{{math|''O''(''n'' log ''n'')}}'''}}-algoritme.

Når innmatningen er et tilfeldig antall permutasjoner, har «dreiepinnen» en tilfeldig rangering, og det er ikke garantert at den er i de midterste 50%. Når vi likevel starter fra en tilfeldig permutasjon, har «dreiepinnen» i hvert rekursive kall en tilfeldig rangering i sin liste, og vil således være blant de midterste 50 % omkring halvparten av tiden. Dette er godt nok. Forestill deg at du kaster en mynt: [[Mynt]] betyr at «dreiepinnens» rangering er i midten av 50%, krone betyr at den ikke er det. Du kaster mynten igjen og igjen inntil du får ''k'' hoder. Selv om dette ville ta lang tid, er i gjennomsnitt bare {{math|2''k''}} kast påkrevet, og sjansen for at du ikke vil få ''k'' hoder etter ''k'' kast er høyst usannsynlig. Dette kan bli gjort enda mer rigoriøst ved å benytte [[Chernoffavgrensninger]]. Ut fra samme argument vil Quicksort's  rekursjon opphøre etter i gjennomsnitt en kalldybde på bare {{mono|'''<math>2 \log_{4/3} n</math>'''}}. Men hvis gjennomsnittlig kalldybde er {{mono|'''{{math|''O''(log ''n'')}}'''}}, og hvert nivå av kalltreet prosesserer på det meste ''n'' elementer, da vil den totale mengden med arbeid i gjennomsnitt være {{mono|'''{{math|''O''(''n'' log ''n'')}}'''}}. Algoritmen behøver ikke å verifisere at «dreiepinnen» er i den midterste halvdel. Hvis vi møter en konstant på en brøkdel av tiden, vil det være nok for den ønskede kompleksitet.

===== Bruk av recurrency =====
{{seksjonstubb}}
Beskrivelse	Hva du skriver	Hva du får
Kursiv	''Kursiv tekst''	Kursiv tekst
Fet	'''Fet tekst'''	Fet tekst
Fet & kursiv	'''''Fet & kursiv tekst'''''	*Fet & kursiv tekst*