Begreper & formler

Kan finnes med $2n-2$ sammenligninger ved å holde styr på nåværende min og maks.

Bruker tilfeldig pivot (som quicksort) for å finne ønsket element i forventet $O(n)$ tid.

Bruker ‘median-av-medians’ for å garantere $O(n)$ i verste tilfelle.

Samme operasjon som i quicksort – brukes til å plassere pivot på korrekt posisjon.