Quicksort explained: how it works, code and complexity

The idea in plain words

1. Choose a pivot element, for example the last element, or a random one.
2. Partition: move every element smaller than the pivot to its left and every larger element to its right. The pivot is now in its final sorted position.
3. Recursively sort the part left of the pivot and the part right of it. Nothing needs to be combined afterwards.

Merge sort does easy splitting and hard merging. Quicksort is the opposite: the partition does the work, and joining the halves is free because they are already in the right place in the same array.

Worked example: one Lomuto partition

Partition [10, 80, 30, 90, 40, 50, 70] with the last element, 70, as pivot. Index i marks the end of the region of elements smaller than the pivot; j scans from left to right.

70 is now at index 4, its final position. Quicksort then sorts [10, 30, 40, 50] and [90, 80] separately.

Python implementation

import random

def partition(a, lo, hi):
    """Lomuto partition of a[lo..hi] around a random pivot."""
    r = random.randint(lo, hi)
    a[r], a[hi] = a[hi], a[r]       # move the pivot to the end
    pivot = a[hi]
    i = lo - 1
    for j in range(lo, hi):
        if a[j] < pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i + 1], a[hi] = a[hi], a[i + 1]
    return i + 1

def quicksort(a, lo=0, hi=None):
    """Sort list a in place."""
    if hi is None:
        hi = len(a) - 1
    while lo < hi:
        p = partition(a, lo, hi)
        if p - lo < hi - p:           # recurse on the smaller side
            quicksort(a, lo, p - 1)
            lo = p + 1
        else:
            quicksort(a, p + 1, hi)
            hi = p - 1
    return a

print(quicksort([10, 80, 30, 90, 40, 50, 70]))   # [10, 30, 40, 50, 70, 80, 90]
print(quicksort([3, 3, 3, 1]))                   # [1, 3, 3, 3]

Recursing into the smaller side and looping on the larger side keeps the stack depth at O(log n) even in the worst case. A short, non-in-place version is popular for explaining the idea, but it allocates new lists at each level:

def quicksort_simple(items):
    if len(items) <= 1:
        return items
    pivot = items[len(items) // 2]
    less = [x for x in items if x < pivot]
    equal = [x for x in items if x == pivot]
    greater = [x for x in items if x > pivot]
    return quicksort_simple(less) + equal + quicksort_simple(greater)

print(quicksort_simple([5, 2, 9, 2, 7]))   # [2, 2, 5, 7, 9]

Time and space complexity

The classic worst case is a fixed first-or-last-element pivot on input that is already sorted or reverse sorted: each partition removes only the pivot, giving n levels of O(n) work. A random pivot makes this extremely unlikely for any input.

How quicksort compares with other sorts

Quicksort is not stable: a partition swap can move an element past an equal one. It usually beats merge sort and heapsort on arrays in memory because its inner loop is simple, it works in place and it accesses memory mostly sequentially. Introsort, used by many C++ standard library implementations of std::sort, starts with quicksort and switches to heapsort if the recursion gets too deep, which guarantees O(n log n).

Pivot choices, variants and common mistakes

• Pivot choice: first or last element (simple, but O(n²) on sorted input), random element, or median of three (first, middle, last).
• Hoare partition: two indexes move toward each other and swap pairs that are on the wrong side. It does fewer swaps than Lomuto on average.
• Three-way partition (Dutch national flag): splits into less, equal and greater. It makes arrays with many duplicate keys fast; plain Lomuto degrades to O(n²) when all keys are equal.
• Dual-pivot quicksort uses two pivots and three parts; Java uses it to sort arrays of primitive types.
• Quickselect uses one partition and recurses into only one side to find the k-th smallest element in O(n) average time.

When to use quicksort

Quicksort is a good default for sorting arrays in memory when stability is not needed. In Python, use sorted() or list.sort() instead; they use Timsort, which is stable and fast on partially sorted data. Implementing quicksort is a very common interview task, often followed by questions about the worst case, pivot choice, stability, or using quickselect to find the k-th largest element.