Verfahren

Ein Feld wird in zwei Teilfelder aufgeteilt und anschließend jeweils genau ein Element des einen Teilfeldes mit einem Element des anderen Teilfeldes verglichen. Dadurch befindet sich das größte Element im rechten und das kleinste im linken Teilfeld. Die beide Teilfelder werden rekursiv genauso weitergeteilt, wobei immer nur eine Hälfte weiterverfolgt wird. Am Ende befindet sich das größte Element am Feldende und das kleinste am Feldanfang. Diese Schritte werden solange am kleineren Feld (Feld ohne die beiden "sortierten" Elemente) wiederholt, bis das gesamte Feld sortiert vorliegt.

Die Idee stammt aus der Suche des größten und kleinsten Elementes eines Feldes. Man vergleicht jeweils das erste Element mit dem zweiten, das dritte mit dem vierten, ... und tauscht ggf. die Elemente aus. Am Ende bfindet sich das kleinste Element mit Sicherheit in dem Teilfeld mit den geradzahligen Positionsnummern und das größte in dem anderen Teilfeld. Jetzt wird das kleinste/größte Element normal gesucht. Statt 2n Vergleiche benötigt diese Suche nur 3/2*n Vergleiche. Und die selbe Idee kann etwas abgewandelt auch als Sortieralgorithmus realisiert werden.