Quicksort

Updated September 30, 20263 min read

In short

Quicksort is a divide and conquer sorting algorithm that partitions items around a chosen pivot, then sorts the smaller and larger groups the same way.

What is quicksort?

Quicksort is a sorting algorithm that chooses one item as the pivot, rearranges the list so that everything smaller than the pivot comes before it and everything larger comes after it, and then sorts those two parts the same way. After partitioning, the pivot is already in its final position, so no merge step is needed. It was developed by Tony Hoare in 1959 and is still one of the fastest general-purpose sorting algorithms in practice.

On average, quicksort runs in O(n log n) time, because a reasonable pivot splits the items roughly in half and each level of partitioning processes n items. The worst case is O(n^2), which happens when the pivot is repeatedly the smallest or largest item, for example when a naive version that always picks the first item is given data that is already sorted. Implementations avoid this by choosing a random pivot or the median of three items. Partitioning swaps items within the array itself, so quicksort sorts in place, needing only O(log n) extra memory for recursion when it handles the smaller part first.

Picture sorting a class by height: pick one student, send everyone shorter to the left and everyone taller to the right, then repeat within each group until every group has one person. Quicksort's small memory footprint and cache-friendly access to neighboring items make it a common default. Introsort, a hybrid that starts with quicksort and switches to heap sort if the recursion gets too deep, is used by many implementations of C++'s std::sort, and Java sorts arrays of primitive values with a dual-pivot quicksort. The same partitioning idea powers quickselect, which finds the k-th smallest item, such as the median, in O(n) average time.

Quicksort is most often compared with merge sort. Merge sort guarantees O(n log n) and is stable, but it needs O(n) extra memory for arrays; quicksort sorts in place and is usually faster in practice, but its worst case is O(n^2) and it is not stable, so equal items may change their relative order. In short, quicksort does its work while dividing, by partitioning, and merge sort does its work while combining, by merging.

Key takeaways

Quicksort partitions items around a pivot, then sorts each side recursively.
It averages O(n log n) time, but its worst case is O(n^2).
A random or median-of-three pivot makes the worst case very unlikely.
It sorts in place with little extra memory, but it is not stable.
Hybrids such as introsort combine quicksort with heap sort to guarantee O(n log n).

Example

A short, readable quicksort in Pythonpython

import random

def quicksort(items):
    if len(items) <= 1:
        return items  # base case: nothing left to sort
    pivot = random.choice(items)  # a random pivot makes the O(n^2) case unlikely
    smaller = [x for x in items if x < pivot]
    equal = [x for x in items if x == pivot]
    larger = [x for x in items if x > pivot]
    # The pivot group is already in its final place; sort each side the same way
    return quicksort(smaller) + equal + quicksort(larger)

print(quicksort([38, 27, 43, 3, 9, 82, 10]))  # [3, 9, 10, 27, 38, 43, 82]
# Production versions partition in place instead of building new lists

Readers ask

Why is quicksort fast if its worst case is O(n^2)?

With a random or median-of-three pivot, the worst case is extremely unlikely, and the average case is O(n log n) with small constant factors. Quicksort also works in place on neighboring memory, which makes good use of the CPU cache.

Is quicksort stable?

No, the standard in-place version is not stable, because partitioning can swap equal items past each other. If equal items must keep their original order, use merge sort or a stable library sort such as Timsort.

What is the difference between quicksort and merge sort?

Both are divide and conquer sorts that average O(n log n). Quicksort partitions around a pivot and sorts in place but can degrade to O(n^2) and isn't stable, while merge sort splits evenly, always runs in O(n log n), is stable, and needs O(n) extra memory.

Often compared

Merge Sort vs QuicksortMerge sort guarantees O(n log n) time but uses extra memory, while quicksort partitions around a pivot in place and is usually faster, but can slow to O(n²).