Redigerer Kvikksortering (avsnitt)

==== 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'')}}'''}}.