Redigerer Kvikksortering (avsnitt)

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