allgemeines Sortierverfahren zum Sortieren von n Elementen.

Die Idee des Verfahrens besteht darin, die zu sortierende Eingabemenge, die als Feld A[p..r] abgespeichert ist, in zwei nichtleere Teilfelder A[p..q] und A[q+1…r] so umzuordnen, daß jedes in A[p..q] abgespeicherte Element kleiner oder gleich jedem in A[q + 1..r] abgespeicherten Element ist. Der Index q wird hierbei im Rahmen des Partitionsschritts berechnet, die beiden Teilfelder A[p..q] und A[q + 1..r] werden rekursiv nach dem gleichen Schema sortiert. Das so entstehende Feld A[p..q] ist nach diesem Schritt fertig sortiert.

Zentraler Bestandteil des Verfahrens ist der Partitionierungsschritt. Hier wird das an der ersten Stelle abgespeicherte Element A[p] als Dreh- und Angelpunkt δ benutzt. Der Partitionierungsschritt teilt das Feld A[p..r] so auf, daß alle Elemente aus A[p..q] kleiner gleich δ und alle Elemente aus A[q + 1..r] größer oder gleich δ sind.

Quicksort benötigt im schlechtesten Fall c₁ · n² Schritte für eine von n unabhängige Konstante c₁. Dieser Fall liegt gerade dann vor, wenn alle Elemente der Eingabefolge paarweise verschieden und schon sortiert sind. Sind alle Eingabefolgen gleich wahrscheinlich, so benötigt Quicksort im Mittel weniger als c₂ · n · [log₂n] Schritte für eine sehr kleine, von n unabhängige Konstante c₂. Um dieses Mittel auch bei nicht vorliegender Gleichverteilung zu erreichen, wird der Dreh- und Angelpunkt δ zumeist zufällig aus den in A[p..r] abgespeicherten Elementen gewählt. Man spricht in diesem Fall von randomisiertem Quicksort.