Sorting III: Quicksort

Quicksort is a divide-and-conquer sort: partition around a pivot to lock one element in its final spot, then recurse on the two halves.

The core idea

• Partition: pick a pivot, move all smaller values left and all >= values right.
• After partitioning, the pivot sits in its final sorted position and never moves.
• Recurse separately on the left group and the right group.
• One partition places exactly one element correctly.

Lomuto partition scheme

• Uses the last element as pivot; sweeps left to right.
• i = boundary of the “smaller than pivot” region (starts at low - 1).
• j = scanner walking every element.
• Rule: if arr[j] < pivot, advance i and swap arr[i], arr[j]; else keep scanning.
• End: swap pivot into i + 1; return i + 1 as the pivot’s final index.
• arr[j] < pivot (strict) puts values equal to the pivot on the right.

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

Full quicksort

• Base case: section of length 0 or 1 (guard if low < high) does nothing.
• Recurse on low..p-1 and p+1..high (skip the placed pivot at p).
• Works on indices, not sub-list copies, which keeps it memory-light.

def quicksort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        p = partition(arr, low, high)
        quicksort(arr, low, p - 1)
        quicksort(arr, p + 1, high)
    return arr

Complexity

• One partition on length k costs O(k) (one scan, at most one swap per element).
• Total time = work-per-level (O(n)) times number-of-levels.

• Worst case fires when every pivot is the min/max of its section.
• With Lomuto’s last-element pivot, an already sorted list triggers O(n^2).
• Space: in-place, extra memory is the call stack. O(log n) average, O(n) worst.

Avoiding the worst case

• Randomized quicksort: pick a random pivot index, swap it to the end, reuse Lomuto. Expected O(n log n) for any input, including sorted ones.
• Median-of-three: use the median of first, middle, last as pivot (no randomness).
• No fixed input can force the worst case once the pivot is unpredictable.

Quicksort vs merge sort

• Quicksort is usually faster in practice (in-place, good locality, small constants).
• Pick merge sort when a worst-case guarantee or stability is required.

Gotchas

• Recurse on p-1 / p+1, not p (including the pivot again can loop forever).
• Missing the low < high guard causes infinite recursion (RecursionError).
• Quicksort is not stable; swaps reorder equal elements.
• Fixed last/first pivot on sorted data is O(n^2); randomize or use median-of-three.
• Mixing numbers and strings raises TypeError (can’t compare types).