# Quicksort
## Algorithms — The Codex Coding
**URL:** https://thecodex.expert/coding/algorithms/sorting/quicksort/
**Type:** algorithm | **Confidence:** high | **Last verified:** 2026-06-01

## CANONICAL DEFINITION
Quicksort is a comparison-based in-place sorting algorithm that partitions an array around a chosen pivot element — placing all smaller elements before the pivot and all larger after — then recursively sorts each partition, achieving Theta(n log n) expected time with O(log n) space.

## COMPLEXITY
- best: Theta(n log n)
- average: Theta(n log n)
- worst: Theta(n^2)
- space: O(log n)
- stability: not stable

## REQUIRES
algorithms/sorting, concepts/recursion

## ENABLES
algorithms/searching

## COMMONLY CONFUSED WITH
not always faster than merge sort; not stable; O(log n) stack can overflow in degenerate cases

## SOURCES
- Hoare 1962 Computer Journal 5(1)
- CLRS 4th ed. §7
- Musser 1997 SPE 27(8) Introsort
- Yaroslavskiy 2009 dual-pivot OpenJDK

*The Codex Coding — thecodex.expert/coding/ — Free forever — Mumbai, India*