Quicksort

Quicksort is a divide-and-conquer comparison sort that picks a pivot, partitions the array around it, and recursively sorts the partitions. In practice it is the fastest general-purpose sort on most inputs, which is why it underlies std::sort in C++ and many language standard libraries.

Complexity

Best	Average	Worst	Space (Worst)
`Ω(n log n)`	`Θ(n log n)`	`O(n²)`	`O(log n)`

How it works

Pick a pivot (commonly the last, first, or a random element). Partition: move all elements ≤ pivot to the left, all > pivot to the right. Recurse on each side. Worst case O(n²) hits when pivots are consistently extreme (e.g. already-sorted input with a fixed last-element pivot); randomization or median-of-three avoids this in practice.

Python implementation

def quicksort(arr):
    """In-place Lomuto-partition quicksort."""
    def _sort(lo, hi):
        if lo >= hi:
            return
        pivot = arr[hi]
        i = lo
        for j in range(lo, hi):
            if arr[j] <= pivot:
                arr[i], arr[j] = arr[j], arr[i]
                i += 1
        arr[i], arr[hi] = arr[hi], arr[i]
        _sort(lo, i - 1)
        _sort(i + 1, hi)
    _sort(0, len(arr) - 1)
    return arr


print(quicksort([3, 6, 1, 8, 2, 9, 4]))  # [1, 2, 3, 4, 6, 8, 9]

Trade-offs

In-place, only O(log n) recursion-stack space.
Not stable — equal keys may swap order.
Worst-case O(n²); use random or median-of-three pivots in production.
Cache-friendly thanks to sequential partition passes.

← Back to Algorithms