Quicksort is a sorting algorithm developed by Tony Hoare that, on average, makes O(nlog n) comparisons to sort n items. In the worst case, it makes O(n²) comparisons, though this behavior is rare. Quicksort is often faster in practice than other O(nlog n) algorithms.^[1] Additionally, quicksort's sequential and localized memory references work well with a cache. Quicksort can be implemented with an in-place partitioning algorithm, so the entire sort can be done with only O(log n) additional space.^[2]
Quicksort (also known as "partition-exchange sort") is a comparison sort and, in

Visualization of the quicksort algorithm. The horizontal lines are pivot values.
Class	Sorting algorithm
Worst case performance	O(n2)
Best case performance	O(n log n)
Average case performance	O(n log n)
Worst case space complexity	O(n) (naive) O(log n) (Sedgewick 1978)

Quicksort is a sorting algorithm developed by Tony Hoare that, on average, makes