Für die Bestimmung des Medians einer Menge von Zahlen ist ein vollständiges Sortieren nicht immer erforderlich. Das ist eine häufig auftretende Berechnung in der Statistik und in verschiedenen anderen Anwendungen der Datenverarbeitung. Zweck: die Zahlen zu sortieren und die mittlere zu betrachten. Am günstigsten ist den Zerlegungsprozeß von Quicksort zu benutzen.

Die Aufgabe der Bestimmung des Medians lautet: Finde aus einer Menge von Zahlen die "k-kleinste"., d.h., diejenige, die an k-ter Stelle steht, wenn man die Zahlen der Größe nach ordnet.

Folgendes Bild zeigt die Zerlegung für unser Beispiel. Um den Median in unserem Sortierbeispiel zu finden, benötigt das Programm nur drei rekursive Aufrufe. Die Datei wird so umgeordnet, daß der Median sich an seinem Platz gefindet, mit kleineren Elementen links und größeren Elementen rechts von ihm.

Der ungünstigste Fall ist etwa der gleiche wie bei Quicksort: Die Benutzung dieser Methode zum Auffinden des kleinsten Elements in einer sortierten Datei würde zu einer quadratische Laufzeit führen.