Quicksort

Quicksort

Animated visualization of the quicksort algorithm. The horizontal lines are pivot values.
Class	Sorting algorithm
Worst-case performance	${\displaystyle O(n^{2})}$
Best-case performance	${\displaystyle O(n\log n)}$ (simple partition) or ${\displaystyle O(n)}$ (three-way partition and equal keys)
Average performance	${\displaystyle O(n\log n)}$
Worst-case space complexity	${\displaystyle O(n)}$ auxiliary (naive) ${\displaystyle O(\log n)}$ auxiliary (Hoare 1962)
Optimal	No

Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959^[1] and published in 1961.^[2] It is still a commonly used algorithm for sorting. Overall, it is slightly faster than merge sort and heapsort for randomized data, particularly on larger distributions.^[3]

Quicksort is a divide-and-conquer algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. For this reason, it is sometimes called partition-exchange sort.^[4] The sub-arrays are then sorted recursively. This can be done in-place, requiring small additional amounts of memory to perform the sorting.

Quicksort is a comparison sort, meaning that it can sort items of any type for which a "less-than" relation (formally, a total order) is defined. It is a comparison-based sort since elements a and b are only swapped in case their relative order has been obtained in the transitive closure of prior comparison-outcomes. Most implementations of quicksort are not stable, meaning that the relative order of equal sort items is not preserved.

Mathematical analysis of quicksort shows that, on average, the algorithm takes ${\displaystyle O(n\log {n})}$ comparisons to sort n items. In the worst case, it makes ${\displaystyle O(n^{2})}$ comparisons.