Quicksort ( ‚schnell‘ und ‚sortieren‘) ist ein schneller,
rekursiver, nicht-
stabiler Sortieralgorithmus, der nach dem Prinzip
Teile und herrsche (lat.
Divide et impera!, engl. ) arbeitet. Er wurde ca. 1960 von
C. Antony R. Hoare in seiner Grundform entwickelt und seitdem von vielen Forschern verbessert. Der Algorithmus hat den Vorteil, dass er über eine sehr kurze innere Schleife verfügt (was die Ausführungsgeschwindigkeit stark erhöht) und ohne zusätzlichen Speicherplatz auskommt (abgesehen von dem für die Rekursion zusätzlichen benötigten Platz auf dem
Aufruf-Stack).