Det är väl känt att prestandan för snabbsort kan förbättras avsevärt genom att välja medianen för ett prov av tre element som pivot för varje partitioneringssteg. Denna variant är lätt generaliserad till prover av storlek s = 2k + 1. För stora prover är partitionerna bättre eftersom medianvärdet för provet gör en mer exakt uppskattning av medianvärdet för den matris som ska sorteras, men mängden ytterligare jämförelser och utbyten till nd medianen för provet ökar också. Vi visar att den optimala provstorleken för att minimera den genomsnittliga totala kostnaden för snabbsort (som inkluderar både jämförelser och utbyten) är s = a p n + o( p n ). Vi ger också ett slutet uttryck för den konstanta faktorn a, som beror på median-nding algoritmen och kostnaderna för elementära jämförelser och utbyten. Ovanstående resultat håller i de flesta situationer, om inte kostnaden för ett byte överstiger den ojämförliga kostnaden för en jämförelse. I detta särskilda fall är det bättre att välja inte medianen för proverna, utan (p + 1) th elementet. Värdet p kan exakt fastställas som en funktion av förhållandet mellan kostnaden för ett byte och kostnaden för en jämförelse. Vi visar också hur man applicerar samma idéer och tekniker på analysen av kvickselect, en general-purpose valalgoritm nära relaterad till quicksort, och få liknande resultat som för quicksort.
I praktiken är det oftast väljs som median i ett urval av tre element, medan teorin tyder på att välja det som medianen för  på ( ε n) element för att minimera jämförelser REF.
Optimal Sampling Strategies in Quicksort and Quickselect
{'venue': 'PROC. OF THE 25TH INTERNATIONAL COLLOQUIUM (ICALP-98), VOLUME 1443 OF LNCS', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}