· Development

When does quicksort hit O(n²)? How standard sorts avoid the worst case

Sorted input, median-of-3 killers and adversarial comparators can push quicksort to quadratic time. This article explains introsort’s depth limit and what C++, Rust, Go and Java actually guarantee.

DevelopmentAlgorithms

Quicksort is taught as O(n log n) on average and O(n²) in the worst case. Which inputs cause that worst case, and does your language’s built-in sort carry the same risk? Quicksort itself can still go quadratic. Many standard libraries guard against it, but whether that guarantee belongs to the specification or only an implementation note depends on the language.

When partitions keep coming out lopsided

Quicksort picks a pivot, splits the remaining elements into those smaller and larger than it, and sorts each side. If every split is roughly even, the recursion goes about log₂ N levels deep. Each level does work proportional to N, giving N log N overall.

If the splits keep landing on one side and the depth grows in proportion to N, the total becomes N².

The simplest example is an implementation that always takes the first element as its pivot and receives an already sorted array. The pivot is always the minimum, leaving one side empty. The comparison count is:

(n−1)+(n−2)+…+1 = n(n−1)/2

For n = 1,000, that is 499,500 comparisons.

A better pivot still leaves a worst case

Median-of-3 uses the median of the first, middle and last elements as the pivot. It handles sorted input well, but it does not remove the worst case. In a 1997 paper, David Musser gave a permutation for N divisible by 4 that makes median-of-3 partitioning split off only two elements at each step. This “median-of-3 killer” makes median-of-3 quicksort take Ω(N²) time. The paper notes that HP’s STL sort worked this way at the time.

Random pivots make a long run of bad splits very unlikely, but the worst-case bound remains N². In a 1999 paper, M. D. McIlroy built an adversarial comparison function that watches the order of comparisons and fixes values on the fly. Under a few assumptions, it can drive randomized quicksort implementations into quadratic time too.

In McIlroy’s table, the median-of-3 qsort in Irix 6.4 made about 0.25n² comparisons against this adversary. That was one measurement of one implementation from around 1998. It is not a general coefficient, nor is it a proven ultimate worst case for that implementation.

Introsort: putting a limit on depth

Musser’s introsort partitions like median-of-3 quicksort. Once the depth reaches 2⌊log₂ N⌋, it hands the remaining range to heapsort. Heapsort remains N log N in the worst case, and the paper proves a Θ(N log N) worst-case bound for introsort. On most inputs, it behaves almost exactly like quicksort.

A heap is not a sorted list explains how heaps are laid out. As Musser’s paper notes, introsort is not stable.

What the language documentation guarantees

C++. The complexity of std::sort used to say “approximately N log N comparisons on the average”, with a footnote recommending stable_sort or partial_sort when worst-case behavior mattered. LWG issue 713, opened in 2007, pointed to introsort and proposed changing the requirement to O(N log N). Its resolution went into the 2008 committee draft. The [sort] clause of the current working draft requires O(N log N) comparisons and projections without prescribing an algorithm.

Rust. The main text of the slice::sort_unstable documentation says the sort is unstable, in-place and O(n log n) in the worst case. Its use of ipnsort, which combines quicksort and heapsort, appears in a separate “Current implementation” section.

Go. The sort.Sort documentation says it makes O(n log n) calls to Less and Swap. The rewrite to pattern-defeating quicksort is documented in the Go 1.19 release notes.

Java. The JDK 8 implementation note for Arrays.sort(int[]) says its Dual-Pivot Quicksort offers O(n log n) performance “on many data sets that cause other quicksorts to degrade to quadratic performance.” JDK 25 says “on all data sets.” The Arrays class documentation identifies these algorithm descriptions as implementation notes rather than part of the specification.

If you write your own

If you write your own quicksort, pairing a depth limit with a fallback algorithm is safer than relying on pivot selection alone. For a built-in sort, check the documentation for the version you use. A guarantee in the specification is different from a note describing the current implementation.

The documentation was checked on 5 October 2026.

Papers and documentation used

Back to the blog