Quick Sort

Quick sort is also divide-and-conquer, but it divides differently from merge sort: instead of always splitting at the midpoint and doing the hard work in the merge step, it picks a pivot element and partitions the list around it — everything smaller goes left, everything bigger goes right — so the hard work happens in the split, and the "combine" step is nothing at all (the pieces are already in their final relative order once every partition is sorted). It's also the first sort in this track that's genuinely in-place.

Divide and Conquer via Pivot Partitioning

Pick any element as the pivot, then rearrange the list so every element smaller than the pivot ends up before it and every element larger ends up after it. The pivot is now in its final sorted position. Recursively apply the same process to the sub-list left of the pivot and the sub-list right of it.

def quick_sort(items, low=0, high=None):
    if high is None:
        high = len(items) - 1

    if low >= high:
        return items                       # base case: 0 or 1 element

    pivot_index = partition(items, low, high)
    quick_sort(items, low, pivot_index - 1)   # recurse left of pivot
    quick_sort(items, pivot_index + 1, high)  # recurse right of pivot
    return items

Time complexity: O(n log n) average case — see the full derivation and worst-case analysis further down this page. Space complexity: O(log n) average — recursion stack depth matches the height of a balanced partition tree.

The Lomuto Partition Scheme, Fully Worked

The Lomuto scheme picks the last element as the pivot. It walks index j across the range; whenever it finds an element smaller than the pivot, it swaps that element into the next slot after a boundary pointer i, which tracks the end of the "confirmed smaller than pivot" region. At the end, the pivot is swapped into place right after that region — entirely in place, no extra list allocated.

def partition(items, low, high):
    pivot = items[high]           # Lomuto scheme: pivot is always the last element
    i = low - 1             # boundary: index of last element known to be < pivot

    for j in range(low, high):
        if items[j] < pivot:
            i += 1
            items[i], items[j] = items[j], items[i]   # bring smaller element into the "< pivot" region

    # place the pivot right after the smaller-than-pivot region
    items[i + 1], items[high] = items[high], items[i + 1]
    return i + 1                # pivot's final, sorted index

Trace on [10, 80, 30, 90, 40] with pivot = 40 (last element): j=0, items[0]=10<40 → i=0, swap items[0] with items[0] (no-op). j=1, items[1]=80, not <40, skip. j=2, items[2]=30<40 → i=1, swap items[1] and items[2] → [10, 30, 80, 90, 40]. j=3, items[3]=90, not <40, skip. Loop ends with i=1, so swap items[2] (80) with items[4] (pivot 40) → [10, 30, 40, 90, 80]. Pivot 40 is now at index 2, its correct sorted position, with everything smaller to its left and everything larger to its right.

Time complexity: O(n) — the single pass over indices low..high does one comparison per element. Space complexity: O(1) — partitioning happens in place with only a couple of index variables and Python's tuple-swap syntax.

Average O(n log n) vs Worst Case O(n²)

Just like merge sort's recursion tree, quick sort's recursion depth depends entirely on how balanced each partition is. If the pivot consistently splits the list into two roughly equal halves, you get log n levels of partitioning, each doing O(n) work — O(n log n) overall, same shape as merge sort's derivation. But if the pivot is consistently the smallest or largest element, one side of the partition is empty and the other has everything else.

# Already-sorted input, using Lomuto's "always pick the last element" rule:
items = [1, 2, 3, 4, 5]
quick_sort(items)

Space complexity: O(log n) average (recursion stack depth matches the balanced recursion tree height) but O(n) worst case (recursion depth matches the number of levels, which becomes n in the degenerate case above).

The Fix: Random Pivot Selection

The worst case above isn't really about quick sort being fragile — it's about the specific rule "always use the last element," which is trivially defeated by already-sorted (or reverse-sorted) input, a very common case in practice. Python's standard random module removes that predictability: swap a randomly chosen element into the last position before running the exact same Lomuto partition. An adversary can no longer construct a guaranteed-bad input, since the pivot choice isn't fixed.

import random

def partition_randomized(items, low, high):
    random_index = random.randint(low, high)
    items[random_index], items[high] = items[high], items[random_index]  # move random element into the pivot slot
    return partition(items, low, high)      # then partition exactly as before


def quick_sort_randomized(items, low=0, high=None):
    if high is None:
        high = len(items) - 1
    if low >= high:
        return items
    pivot_index = partition_randomized(items, low, high)
    quick_sort_randomized(items, low, pivot_index - 1)
    quick_sort_randomized(items, pivot_index + 1, high)
    return items

Time complexity: expected O(n log n) — randomization makes the worst-case input pattern from above vanishingly unlikely rather than eliminating O(n²) entirely (an adversary who could predict random.randint's output could still theoretically construct a bad case). Space complexity: O(log n) expected, same reasoning as above.

Why Quick Sort Often Beats Merge Sort in Practice