Redigerer Kvikksortering (avsnitt)

====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».