# choose pivotswap a[1,rand(1,n)]# 2-way partitionk = 1 for i = 2:n, if a[i] < a[1], swap a[++k,i] swap a[1,k]→ invariant: a[1..k-1] < a[k] <= a[k+1..n]# recursive sortssort a[1..k-1] sort a[k+1,n]

- Not stable
- O(lg(n)) extra space (see discussion)
- O(n
^{2}) time, but typically O(n·lg(n)) time - Not adaptive

When carefully implemented, quick sort is robust and has low overhead. When a stable sort is not needed, quick sort is an excellent general-purpose sort -- although the 3-way partitioning version should always be used instead.

The 2-way partitioning code shown above is written for clarity rather than optimal
performance; it exhibits poor locality, and, critically, exhibits
O(n^{2}) time when there are few unique keys.
A more efficient and robust 2-way partitioning method is given in
Quicksort is Optimal
by Robert Sedgewick and Jon Bentley. The robust partitioning produces
balanced recursion when there are many values equal to the pivot,
yielding probabilistic guarantees of O(n·lg(n))
time and O(lg(n)) space for all inputs.

With both sub-sorts performed recursively, quick sort
requires O(n) extra space for the recursion stack
in the worst case when recursion is not balanced. This is exceedingly unlikely to occur, but it can be avoided
by sorting the *smaller* sub-array recursively first; the second sub-array sort is a tail
recursive call, which may be done with iteration instead. With this optimization,
the algorithm uses O(lg(n)) extra space in the worst case.

- Click on above to restart the animations in a row, a column, or the entire table.
- Click directly on an animation image to start or restart it.
- Click on a problem size number to reset all animations.

- Black values are sorted.
- Gray values are unsorted.
- Dark gray values denote the current interval.
- A pair of red triangles mark k and i (see the code).

*Algorithms in Java, Parts 1-4, 3rd edition*
by Robert Sedgewick.
Addison Wesley, 2003.

*Programming Pearls*
by Jon Bentley.
Addison Wesley, 1986.

*Quicksort is Optimal*
by Robert Sedgewick
and Jon Bentley,
Knuthfest, Stanford University, January, 2002.

Dual Pivot Quicksort: Code and Discussion.

*Bubble-sort with Hungarian ("Csángó") folk dance * YouTube video, created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania.

*Select-sort with Gypsy folk dance * YouTube video, created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania.

Sorting Out Sorting, Ronald M. Baecker with the assistance of David Sherman, 30 minute color sound film, Dynamic Graphics Project, University of Toronto, 1981. Excerpted and reprinted in SIGGRAPH Video Review 7, 1983. Distributed by Morgan Kaufmann, Publishers. Excerpt.