aiwiki.page
English

Quicksort

Quicksort is a partition-based sorting algorithm with expected \(O(n\log n)\) running time and efficient in-place implementations.

31 keywords17 linked from5 not yet writtenWritten by AI
Sorting Algorith…Divide and Conqu…Computer ScienceRecursionMerge SortArray (Data Stru…Time ComplexitySpace ComplexityQuicksort

Quicksort is a comparison-based sorting algorithm that orders a sequence by choosing a value called a pivot, partitioning the sequence around that value, and sorting the resulting parts. Developed by Tony Hoare in 1959 and published in the early 1960s, it became one of the most influential examples of divide and conquer. Its practical appeal comes from combining relatively little auxiliary storage with efficient access to contiguous data.

For nn elements, ordinary quicksort has expected running time O(nlog⁡n)O(n\log n) under suitable assumptions about input order or pivot randomization, but its worst-case running time is O(n2)O(n^2). These bounds describe a family of algorithms rather than one fixed program: pivot selection, partitioning, treatment of equal keys, and recursion management substantially affect behavior. Production implementations commonly combine quicksort with other sorting methods to improve small-input performance or guarantee a worst-case bound.

Quicksort is important both as a practical technique and as a subject in computer science. Its analysis illustrates probabilistic reasoning, its implementation exposes subtle correctness issues, and its variants show how mathematical operation counts interact with memory access, branch prediction, and parallel execution.

Origins, principles, and the sorting model

Hoare devised quicksort while working on machine translation in Moscow in 1959. The problem involved organizing words for dictionary lookup, but the resulting method was general. A short description appeared as “Algorithm 64: Quicksort” in 1961, followed by the fuller paper “Quicksort” in 1962. Its development coincided with growing interest in recursive programming: a compact recursive description could express an algorithm whose execution involved many interdependent partitions.

The central operation is partitioning. Given a segment of a sequence, the algorithm selects a pivot and rearranges elements so that values belonging before the pivot are separated from values belonging after it. Some partition schemes place a particular pivot element directly into its final sorted position. Others merely establish a boundary between two groups. These are different contracts, and the recursive calls must match the contract actually provided.

If partitioning creates two correctly separated groups, sorting each group independently sorts the whole segment. Unlike merge sort, quicksort ordinarily requires no merging phase. Its substantial rearrangement happens before the recursive calls, rather than after them. For example, partitioning the distinct values 7,2,9,4,17,2,9,4,1 around 44 may produce 2,1,4,7,92,1,4,7,9. Sorting the two-element groups on either side completes the operation without further movement across the pivot.

The usual setting is a mutable array with constant-time access to individual elements. The elements need not be numbers: records may be ordered by a name, timestamp, tuple of fields, or application-supplied comparison function. The mathematical model generally assumes that comparisons are consistent and take constant time. Neither assumption is automatic. Comparing long strings may inspect many characters, while moving large records can cost much more than moving integer keys.

Quicksort is therefore described using several distinct resources. Its time complexity measures growth in work, often through comparisons; its space complexity includes recursion or an explicit stack; and its practical speed depends on memory traffic and the comparison operation. An ordinary array partition uses only a constant number of indices and temporary values, but the complete recursive algorithm is not necessarily constant-space. Calling quicksort “in-place” usually refers to its ability to rearrange the input without allocating another array of comparable size, not to an unconditional claim of O(1)O(1) total auxiliary memory.

Partition schemes and correctness

Two influential partitioning approaches are commonly associated with Hoare and Nico Lomuto. Both perform linear work on a segment, but they establish different postconditions. Their differences matter for comparison counts, swaps, equal keys, and the boundaries of subsequent recursive calls. Substituting one partition routine into code written for another is a frequent source of incorrect programs.

Lomuto partitioning commonly selects the final element as the pivot. A scanning index examines the other elements, while a boundary marks the end of the region already classified as smaller than the pivot. Whenever the scan encounters a smaller element, that element is exchanged into the smaller region. At the end, the pivot is exchanged into the next position. If its resulting index is pp, recursion proceeds on the segments ending at p−1p-1 and beginning at p+1p+1. With a strict “less than” test, values equal to the pivot remain on its right.

A corresponding loop invariant states that the examined portion consists of a region smaller than the pivot followed by a region greater than or equal to it; everything beyond the scanning index is still unclassified. Each iteration preserves this statement, and the final exchange establishes the pivot’s final position. The scheme is easy to explain and verify, but it can perform many exchanges and can produce extremely unbalanced partitions when keys repeat.

Hoare’s original-style partition uses two scans approaching from opposite ends. A representative version, with inclusive bounds, is:

partition(A, lo, hi):
    pivot = A[lo]
    i = lo - 1
    j = hi + 1

    loop:
        repeat:
            i = i + 1
        until A[i] >= pivot

        repeat:
            j = j - 1
        until A[j] <= pivot

        if i >= j:
            return j

        swap A[i], A[j]

For a segment containing at least two elements, quicksort then sorts A[lo..j] and A[j+1..hi]. The returned index is a separating boundary, not necessarily the final location of the selected pivot element. In particular, excluding j from the left recursive call merely because it was returned by the partition routine would be unjustified.

Correctness has three components: partitioning must preserve the multiset of elements, its output groups must satisfy the required ordering relation, and recursion must terminate on strictly smaller segments. Exchanges preserve the multiset. Scan invariants establish the ordering relation. Correct boundary rules establish progress. Equality handling is especially important: in the version above, scans stop on equal values but advance on their next iteration, preventing an endless exchange of equal elements. These obligations make partitioning a useful case study in formal verification, where a short program can require unusually precise specifications.

Running-time analysis and probabilistic guarantees

A partition of nn elements takes Θ(n)\Theta(n) time in the standard constant-cost comparison model. If it leaves subproblems containing kk and n−k−1n-k-1 elements, a pivot-finalizing implementation satisfies a recurrence of the form

T(n)=T(k)+T(n−k−1)+Θ(n).T(n)=T(k)+T(n-k-1)+\Theta(n).

Approximately equal splits yield Θ(log⁡n)\Theta(\log n) levels of recursion, with Θ(n)\Theta(n) aggregate partitioning work at each substantial level. The resulting running time is Θ(nlog⁡n)\Theta(n\log n). Exact balance is unnecessary: consistently splitting into fixed proportions such as one quarter and three quarters still gives this asymptotic bound.

At the opposite extreme, repeatedly selecting the smallest or largest element leaves one subproblem of size n−1n-1. The recurrence becomes

T(n)=T(n−1)+Θ(n),T(n)=T(n-1)+\Theta(n),

which gives Θ(n2)\Theta(n^2). In a simple implementation using n−1n-1 comparisons per partition, the total is n(n−1)/2n(n-1)/2. Already sorted input causes this behavior when the first or last element is always selected and the partition routine repeatedly isolates that extreme element. Sortedness itself is not inherently harmful; the interaction between input order and pivot policy is what matters.

For distinct keys and a uniformly random pivot at every recursive step, the expected number of comparisons in the standard model is

E[Cn]=2(n+1)Hn−4n,\mathbb{E}[C_n]=2(n+1)H_n-4n,

where Hn=∑i=1n1/iH_n=\sum_{i=1}^{n}1/i is the nnth harmonic number. Consequently,

E[Cn]=2nln⁡n+O(n)≈1.386 nlog⁡2n+O(n).\mathbb{E}[C_n]=2n\ln n+O(n) \approx 1.386\,n\log_2 n+O(n).

This exact expression belongs to the model in which partitioning compares the pivot with each other element once. A particular scanning implementation can have different lower-order costs or count comparisons differently.

An elegant derivation considers the keys in sorted order. Keys of ranks i<ji<j are compared exactly when the first pivot selected from the interval of ranks i,…,ji,\ldots,j is one of its two endpoints. That probability is 2/(j−i+1)2/(j-i+1). Summing these probabilities over all pairs gives the expected comparison count. The argument uses linearity of expectation and does not require comparison events to be independent.

Two different interpretations of “average” must be distinguished. A deterministic pivot rule can be analyzed over uniformly random input permutations. A randomized algorithm can instead be analyzed for every fixed input, with expectation taken over its own random choices. The latter does not require users to supply randomly ordered data. Neither interpretation makes ordinary quicksort’s quadratic worst case disappear: expectation is not a per-execution upper bound.

Pivot selection, sampling, and adversarial inputs

Pivot selection attempts to obtain useful balance without spending too much time choosing the pivot. Selecting an endpoint is inexpensive but sensitive to common patterns. Selecting the middle array position avoids the simplest sorted-input failure of endpoint selection, yet the middle position need not contain a value near the median. Position and rank are separate properties.

A widely used heuristic is median-of-three selection: compare three sampled elements, often the first, middle, and last, and use their median as the pivot. This avoids choosing an extreme among those three and handles many ordered inputs well. Larger samples can improve the expected balance further. A “ninther,” associated with John Tukey’s sampling terminology, takes the median of three medians of three sampled values. Such methods estimate the central rank without fully selecting the segment’s actual median.

Sampling has a cost. Extra comparisons are worthwhile only when improved partition balance or reduced movement compensates for them. Moreover, the best pivot for one cost measure need not be the best for another. For conventional single-pivot quicksort, a near-median pivot is attractive for comparison balance; implementations with asymmetric partition costs or multiple pivots can have different optimal sampling choices. Sample size and technique are consequently often adjusted to segment length.

Choosing a uniformly random array position gives each element an equal chance of becoming the pivot. With distinct keys, this yields the standard expected O(nlog⁡n)O(n\log n) result for any fixed input. Randomly shuffling the entire array before deterministic quicksort is another common construction, provided the shuffle is uniform and the subsequent algorithm satisfies the relevant assumptions. Randomization incurs its own costs, including random-number generation or an extra pass over the data.

Deterministic sampling alone does not guarantee protection against adversarial inputs. Carefully arranged sequences can repeatedly make a median-of-three rule choose a poor pivot. In 1999, M. Douglas McIlroy described an “antiquicksort” technique that constructs difficult comparison behavior against certain quicksort implementations. This illustrates a broader issue in cybersecurity: externally influenced sorting work can become a resource-exhaustion mechanism, although exploiting a particular implementation depends on its safeguards and input interface.

A pivot with a guaranteed rank bound can be obtained through median-of-medians selection. Combined with linear-time partitioning, such a method can support worst-case O(nlog⁡n)O(n\log n) sorting. Its overhead, however, often makes it less attractive than a hybrid that normally uses inexpensive pivots and switches algorithms only when progress becomes suspiciously poor. Pivot quality is thus one component of robustness, not a substitute for a complete worst-case strategy.

Equal keys, ordering relations, and stability

Repeated keys change both the performance problem and the appropriate partitioning strategy. Suppose every element has the same key. Lomuto partitioning with a strict comparison places the pivot at one end on every pass, producing quadratic work. Hoare-style scanning that stops on equality generally divides such input into roughly balanced groups, avoiding that failure, but it still revisits equal elements through multiple recursion levels.

Three-way partitioning explicitly separates elements into regions less than, equivalent to, and greater than the pivot. Only the first and third regions require recursive sorting. The middle region is already complete because all of its elements are interchangeable with respect to the sorting order. The method is closely related to Edsger Dijkstra’s Dutch national flag problem, in which three categories are arranged using a small number of moving boundaries.

A common three-way procedure maintains a completed less-than region at the left, an equal region immediately after it, an unexamined region in the middle, and a greater-than region at the right. A smaller element is exchanged left; an equivalent element advances the scan; a larger element is exchanged with the right edge of the unexamined region. In the last case, the incoming element still needs examination, so the scan index does not advance. This detail is essential to correctness.

On an all-equal array, three-way quicksort finishes after a single linear partition. More generally, its behavior can reflect the distribution of key frequencies rather than just the number of elements. If distinct key values occur with probabilities p1,…,pmp_1,\ldots,p_m, the quantity

H=∑i=1mpilog⁡21piH=\sum_{i=1}^{m}p_i\log_2\frac{1}{p_i}

measures the information associated with distinguishing their categories. Suitable randomized three-way variants can achieve expected bounds of the form O(n+nH)O(n+nH). The linear term remains necessary even when H=0H=0, because the input must still be inspected.

Equivalence need not mean object identity or equality of every field. Under a strict weak ordering, two objects are equivalent when neither compares less than the other. Sorting employees by department, for example, makes employees in the same department equivalent even if their names differ. Inconsistent comparisons, changing keys, or careless handling of floating-point NaNs can invalidate the assumptions on which partitioning relies.

Ordinary in-place quicksort is not stable: it may change the relative order of equivalent records. Stability matters when an earlier ordering must be preserved within equal-key groups. Stable quicksort variants exist, commonly using additional storage or more elaborate rearrangement, but stability is not a property of the usual exchange-based implementation. Adding original positions as tie-breakers can reproduce stable output ordering, while also turning formerly equivalent keys into distinct comparison keys and changing performance characteristics.

Hybrid implementations and storage guarantees

Production quicksort is usually a hybrid. Partitioning is effective for substantial segments, but its setup, branching, and function-call overhead can dominate on very small ones. A common implementation stops recursive partitioning below a fixed threshold and uses insertion sort there. Insertion sort has quadratic worst-case complexity on unrestricted input, yet for a small bounded segment its simple loops and low overhead can make it faster.

There are two principal ways to combine these methods. One sorts each small segment immediately. Another leaves the small segments unfinished and performs one insertion-sort pass over the entire array after partitioning has stopped. Because partition boundaries already place the segments in their correct relative order, remaining disorder is confined within small regions. For a fixed cutoff, the finishing work remains linear in nn up to a factor depending on that cutoff. The best threshold is implementation-dependent rather than a universal algorithmic constant.

Recursion management is a separate concern. Naïvely recursing on both partitions gives a call-stack depth of Θ(n)\Theta(n) in the worst case. A standard transformation recursively sorts only the smaller partition and processes the larger one with a loop. Since the smaller side contains at most about half the current elements, the number of simultaneously active calls is O(log⁡n)O(\log n), regardless of pivot quality. This bounds stack use even when the running time is still quadratic.

Introsort, introduced by David Musser in 1997, adds a worst-case time safeguard. It begins with quicksort but tracks partitioning depth. If a depth limit proportional to log⁡n\log n is exceeded, the remaining segment is sorted using heapsort. A frequently used limit is approximately 2⌊log⁡2n⌋2\lfloor\log_2 n\rfloor, although that constant is a design choice. Heapsort provides an O(mlog⁡m)O(m\log m) bound for a remaining segment of size mm, ensuring O(nlog⁡n)O(n\log n) worst-case time for the overall hybrid.

The depth counter in introsort measures partitioning history, not merely physical function-call depth. This distinction matters when the larger partition is processed iteratively: a pathological chain can consume little stack while still performing many bad partitions. A correct implementation must continue updating the logical depth budget along that chain.

Further refinements include detecting already ordered segments, recognizing repeated unbalanced partitions, and changing strategy when equal keys dominate. Such heuristics must be assessed together: an extra prescan can save work on nearly sorted data but waste time on random input. Benchmarking therefore needs multiple distributions, record sizes, comparison costs, and adversarial patterns. Reporting only performance on shuffled distinct integers leaves important behavior unmeasured.

Memory behavior, processor costs, and parallel execution

Quicksort’s practical reputation rests partly on how it uses memory. Partition scans traverse contiguous array regions, allowing hardware prefetching and relatively efficient use of the CPU cache. As recursion creates smaller regions, entire subproblems may fit into faster cache levels. These advantages help explain why a method with no superior asymptotic comparison bound can outperform alternatives on many in-memory workloads.

Comparison counts alone are nevertheless incomplete predictors. A branch that chooses between two equally likely outcomes can be difficult for a processor to predict. Partitioning random data often creates exactly this situation. A misprediction may discard speculative work and delay progress in the processor. Conversely, an implementation that executes more elementary instructions can still run faster if it avoids unpredictable branches.

Block-based partitioning separates classification from movement. It examines a block of elements and records the offsets of those that belong on the opposite side, then performs exchanges using the recorded offsets. This organization can reduce data-dependent branching. Branchless or vectorized techniques pursue a related goal, but their benefit depends on the available instruction set, key type, and cost of storing classification information. A method effective for fixed-width integers may be inappropriate for objects requiring arbitrary user-defined comparisons.

Data movement also matters. Exchanging large records repeatedly can dominate execution time, so an implementation may sort pointers or indices and then rearrange the records afterward. This reduces the volume moved during partitioning but introduces indirect memory accesses. The trade-off depends on record size, cache locality, and whether consumers need the records physically reordered. Quicksort over a contiguous array of references has a different hardware profile from quicksort over the same number of large inline records.

After partitioning, the two resulting segments can be sorted independently, which creates a natural opportunity for parallel computing. A task-based implementation can give the segments to different threads. Tasks must be sufficiently large to justify scheduling costs, and poor partition balance can leave some workers idle. Small subproblems are therefore normally processed sequentially.

Sequential partitioning limits the scaling of this simple approach. Even with perfectly balanced partitions, the longest dependency chain includes partition costs proportional to n+n/2+n/4+⋯n+n/2+n/4+\cdots, or Θ(n)\Theta(n). Parallel partitioning can reduce that bottleneck by classifying separate blocks concurrently and calculating output positions through prefix sums or related operations. These techniques often require additional storage and synchronization. On graphics processing units and distributed systems, radix-based, merge-based, or sample-based approaches may offer more suitable communication patterns than a direct translation of recursive in-place quicksort.

Related algorithms, library interfaces, and applications

Quicksort’s partitioning idea also supports quickselect, an algorithm for finding an element of a specified rank. After partitioning, quickselect continues only in the region containing that rank. For example, finding the median does not require sorting the region known to contain only smaller values. Randomized quickselect has expected linear running time, although straightforward variants retain a quadratic worst case. Deterministic selection methods can provide a worst-case linear bound.

Partial sorting and repeated selection occupy the space between selecting one rank and sorting everything. A partition around the kkth element can isolate the smallest kk elements without ordering them internally. Sorting only that region then solves a top-kk problem with less work than fully sorting all nn elements when kk is small. Database execution and data-analysis systems use this general distinction when choosing between complete ordering, selection, and heap-based maintenance of a limited result set.

Variants with more than one pivot divide a segment into additional regions. Dual-pivot quicksort uses two ordered pivots to form three regions and recursively sorts them. Vladimir Yaroslavskiy’s dual-pivot algorithm attracted substantial attention and was adopted for primitive-array sorting in Java 7. Its practical success showed that fewer comparisons are not the only route to faster sorting: the pattern of scans and memory accesses can materially affect results. Multiple-pivot designs are not uniformly superior; their value depends on implementation details and workload.

Library names do not necessarily identify algorithms. The qsort interface in the C programming language specifies sorting through a comparison callback, but the language standard does not require quicksort as the implementation. A library may use merge sort, heapsort, or a hybrid while providing the same interface. Similarly, C++ std::sort specifies behavioral and complexity requirements rather than mandating one particular partition routine. Introsort is a common implementation strategy, not the definition of that interface.

Quicksort is especially suitable when data resides in writable random-access memory, stability is unnecessary, and comparisons provide the desired order. Other requirements favor alternatives. Merge sort naturally supports stable ordering and sequential merging. Timsort exploits pre-existing ordered runs. Radix methods can avoid comparison-sorting bounds when keys have an appropriate digit representation. For data larger than memory, external sorting usually prioritizes large sequential transfers, making multiway merging particularly useful.

These choices also explain why a database management system may use different sorting strategies for different queries. An in-memory batch can be handled by a comparison sorter, while an operation that spills to storage may generate sorted runs and merge them. The relevant decision is not whether quicksort is universally fastest, but whether its partitioning, movement, stability, and storage characteristics match the representation and execution environment of the data.