Sorting III: Quicksort

What quicksort is

Sorting means rearranging a collection of items so they run in order, smallest to largest. A list in Python is an ordered row of values written in square brackets, like [5, 2, 8, 1], and each value sits at a numbered position called an index, counting from 0. Quicksort is one of the most widely used algorithms for putting a list in order.

Quicksort belongs to a family called divide and conquer: it breaks a big problem into smaller pieces of the same kind, solves each piece, and combines the results. It does this using recursion, which is a function calling itself on a smaller input until the input is small enough to answer directly.

The whole idea rests on one move, called partitioning:

1. Pick one value from the list and call it the pivot.
2. Rearrange the list so that every value smaller than the pivot ends up to its left, and every value greater than or equal to the pivot ends up to its right.
3. After that rearrangement the pivot is sitting in its final sorted position. It will never need to move again.
4. Now do the same thing, separately, to the group on the left and the group on the right.

That is the entire algorithm. The clever part is step 3: partitioning does not sort anything on its own, but it locks exactly one element into its correct place and splits the remaining work into two independent halves.

The one idea, in plain words

Suppose the list is [7, 2, 9, 4, 3, 8, 1] and we choose the last value, 1, as the pivot. After partitioning, everything smaller than 1 goes left (there is nothing smaller) and everything else goes right, giving something like [1, 2, 9, 4, 3, 8, 7]. The 1 is now in position 0, which is where 1 belongs in the sorted list. We never touch it again. We then repeat the process on [2, 9, 4, 3, 8, 7].

Each round guarantees one element is placed correctly. Do it enough times and every element gets placed.

Partitioning: the Lomuto scheme

There are a few ways to partition. The clearest for a beginner is the Lomuto partition scheme. It uses the last element as the pivot and sweeps through the rest of the section from left to right with two markers.

• i is the boundary: everything strictly to the left of i is known to be smaller than the pivot. It starts just before the section, so at first “the smaller region” is empty.
• j is the scanner: it walks across every element one at a time.

The rule during the sweep: when the scanned value arr[j] is smaller than the pivot, it belongs in the smaller region, so we grow that region by one (advance i) and swap arr[i] with arr[j] to move the small value in. A swap exchanges the values at two positions. When arr[j] is not smaller than the pivot, we leave it where it is and just keep scanning. At the very end we swap the pivot into position i, which is the first slot of the “not smaller” region, putting it exactly between the two groups.

Here is the partition step on its own, written to run:

def partition(arr, low, high):
    pivot = arr[high]        # choose the last element as pivot
    i = low - 1              # boundary of the "smaller than pivot" region
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]   # swap small value into place
    arr[i + 1], arr[high] = arr[high], arr[i + 1]  # put pivot after the smaller region
    return i + 1             # the pivot's final index

data = [7, 2, 9, 4, 3, 8, 1]
p = partition(data, 0, len(data) - 1)
print(p)      # -> 0
print(data)   # -> [1, 2, 9, 4, 3, 8, 7]

low and high are the first and last indices of the section we are partitioning. Working with indices instead of copying sub-lists is what keeps quicksort memory-light.

Step-by-step trace of one partition pass

Trace partition on [7, 2, 9, 4, 3, 8, 5] with pivot 5 (the last element), low = 0, high = 6, so i starts at -1. Each row shows one value of the scanner j: whether arr[j] < 5, whether we advanced i and swapped, and the full array state after that step. Swapped positions are what changed.

The function returns i + 1 = 3. Read the result: everything left of index 3 (2, 4, 3) is smaller than 5, everything right (9, 8, 7) is 5 or larger, and 5 itself sits at index 3, its final sorted home. Notice partition did not sort the two sides; it only separated them.

The full quicksort

Once partition places one element and hands back its index, quicksort just calls itself on the piece to the left of the pivot and the piece to the right. The base case (the smallest problem, answered without further recursion) is a section of length zero or one, which is already sorted.

def quicksort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:                 # base case: length 0 or 1 does nothing
        p = partition(arr, low, high)
        quicksort(arr, low, p - 1)   # sort the left group
        quicksort(arr, p + 1, high)  # sort the right group
    return arr

print(quicksort([7, 2, 9, 4, 3, 8, 5]))
# -> [2, 3, 4, 5, 7, 8, 9]

The condition low < high is the base case check: if the section has zero or one element there is nothing to do, so recursion stops. The pivot at index p is already final, which is why the two recursive calls skip it (p - 1 and p + 1).

The recursion tree

Each partition splits the current section into two smaller sections, and each of those splits again, so the calls stack up into a tree. Sorting [7, 2, 9, 4, 3, 8, 5] might unfold like this, with each node showing the section being partitioned and the pivot in parentheses that lands in place at that step:

graph TD
    A["[7,2,9,4,3,8,5] pivot 5"] --> B["[2,4,3] pivot 3"]
    A --> C["[9,8,7] pivot 7"]
    B --> D["[2] done"]
    B --> E["[4] done"]
    C --> F["[] done"]
    C --> G["[8,9] pivot 9"]
    G --> H["[8] done"]
    G --> I["[] done"]

Each level of the tree does one full sweep across the elements it covers, and the tree’s depth is how many times the list can be split before every piece has size one. Those two numbers, work-per-level and number-of-levels, are exactly what set the running time.

Complexity: average versus worst case

Big-O notation describes how the amount of work grows as the list length n grows, ignoring constant factors. For quicksort the answer depends entirely on how evenly each partition splits its section.

One partition costs O(k) for a section of length k: it scans each of the k elements once and does at most one swap per element. That is the fixed cost per node in the tree.

Average case: O(n log n) time. When pivots tend to land somewhere in the middle, each section splits into two roughly equal halves. The number of times you can halve n down to 1 is about log2(n), so the tree has about log n levels. Every level together touches all n elements once (the sections at a level do not overlap and cover everything), so each level costs O(n). Total: O(n) per level times O(log n) levels equals O(n log n). The term log n (base 2) is the number of doublings to reach n; for a million elements it is only about 20, which is why n log n is close to linear in practice.

Worst case: O(n^2) time. Suppose every pivot turns out to be the smallest or largest element of its section, so partition splits off nothing on one side and everything-minus-one on the other. Then the sections shrink by just one element per level: n, then n - 1, then n - 2, and the tree is n levels deep instead of log n. The costs n + (n-1) + (n-2) + ... + 1 add up to about n^2 / 2, which is O(n^2). With the Lomuto scheme above, this happens on an already sorted list, because the last element is always the largest and every split is maximally lopsided.

How pivot choice avoids the worst case

The worst case is not bad luck about the data alone; it is bad luck about the pairing of the data with a fixed pivot rule. If an adversary knows you always pick the last element, they can hand you the exact input that triggers O(n^2). The defense is to make the pivot unpredictable so no single input is reliably bad.

Randomized quicksort picks the pivot at random each time, then partitions as usual. With a random pivot, getting an extremely lopsided split every single level becomes astronomically unlikely, and the expected running time is O(n log n) for any input, including sorted ones.

import random

def quicksort_random(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        r = random.randint(low, high)               # pick a random pivot index
        arr[r], arr[high] = arr[high], arr[r]        # move it to the end
        p = partition(arr, low, high)                # reuse Lomuto partition
        quicksort_random(arr, low, p - 1)
        quicksort_random(arr, p + 1, high)
    return arr

print(quicksort_random([1, 2, 3, 4, 5, 6, 7]))
# -> [1, 2, 3, 4, 5, 6, 7]

Swapping the random choice to the end lets us reuse the same Lomuto partition unchanged. Another common tactic is median-of-three: look at the first, middle, and last elements and use their median as the pivot, which makes the sorted-input worst case very unlikely without any randomness. The worst case is still theoretically possible with randomization, but no fixed input can force it, so in practice O(n log n) is what you get.

Space: in-place sorting

Space complexity counts the extra memory an algorithm needs beyond the input itself. Quicksort is in-place: partition rearranges the list by swapping elements within the same array, allocating no new list. The only extra memory is the call stack, the region that holds one stack frame (a small record of arguments and position) per active recursive call.

The stack depth equals the depth of the recursion tree. In the average case that depth is O(log n), so quicksort uses O(log n) extra space. In the worst case the tree is n deep, so the stack can reach O(n). A standard refinement recurses into the smaller side first and loops on the larger side, which caps the stack at O(log n) even in the worst case, but the plain version above is O(log n) average, O(n) worst.

Comparison to merge sort

Merge sort is the other classic O(n log n) divide-and-conquer sort. It splits the list in half by position, sorts each half, then merges the two sorted halves back together. The differences matter when choosing between them.

The trade is clear. Quicksort does its hard work up front in partitioning and needs almost no extra memory, but its worst case is quadratic. Merge sort guarantees O(n log n) no matter the input and is stable (equal elements keep their original order), but it must allocate O(n) scratch space to merge. Quicksort tends to be faster in practice because it works in place with good memory locality and small constant factors, which is why many standard library sorts are quicksort variants. When a hard worst-case guarantee or stability is required, merge sort is the safer pick. Python’s own built-in sorted uses neither of these directly; it uses Timsort, a merge-sort variant tuned for real-world data.

Common pitfalls

• Off-by-one in the recursive calls. The pivot at index p is already final, so recurse on low..p-1 and p+1..high. Writing low..p or p..high includes the pivot again and can loop forever.
• Wrong comparison breaks the split. Lomuto uses arr[j] < pivot to build a “strictly smaller” left region and puts values equal to the pivot on the right. Changing it to <= still sorts correctly but shifts where equal elements land; be deliberate about it.
• Forgetting the base case. Without the low < high guard, sections of size one keep calling themselves and you hit Python’s recursion limit with a RecursionError.
• Assuming quicksort is stable. It is not: swaps during partition can reorder equal elements. If you need equal items to keep their input order, use merge sort or a stable sort.
• Trusting a fixed pivot on sorted data. Always-last (or always-first) pivots turn sorted or reverse-sorted input into the O(n^2) worst case. Randomize the pivot or use median-of-three when the input might already be ordered.
• Comparing incompatible types. Sorting a list that mixes numbers and strings raises TypeError because Python cannot compare them; the same applies to any sort.

Practice

1. By hand, run the Lomuto partition on [3, 6, 1, 8, 2, 4] with the last element 4 as pivot. Write the array after each value of the scanner j, and state the index the function returns.
2. Modify quicksort to also print(arr) immediately after each partition call, run it on [5, 3, 8, 1, 9, 2], and confirm from the output that the pivot returned by each partition never moves again.
3. Explain in two or three sentences why passing an already-sorted list of 10,000 numbers to the fixed-pivot quicksort is slow, and why quicksort_random fixes it. State the time complexity of each case.