Quick Sort

What does one partition actually finish?

Quicksort sorts an array by settling one pivot value, then sorting the ranges on either side. The useful part is the guarantee: every value before the pivot is smaller, and every value after it is at least as large. Neither side has to be sorted yet.

Start with these numbers:

7   2   9   4   3   8   5
                        ↑
                      pivot

Choose the last value, 5, as the pivot. After one partition, our implementation produces:

2   4   3  │ 5 │  9   8   7
 below 5  │   │ at least 5
unfinished  settled  unfinished

Three values are smaller than 5. So 5 belongs at index 3, the fourth position. But [2, 4, 3] and [9, 8, 7] still need work. Partitioned does not mean sorted.

This written lesson and lab are ready to use. The new video is in production; there is no public video link yet.

Give each index a job

We use a last-pivot, strict-less-than version of Lomuto partition. Here is what its regions mean before each comparison:

boundary is the next place for a small value. scan is the value to check now. Both start at lo. An empty smaller region is fine: no small values have been found yet.

When the scan finds 2, it belongs before 5. Swap it with 7 at the boundary. The displaced 7 is already known to be at least 5, so it can stay in the checked region. Move the boundary right by one.

Every comparison has a reason, including the ones that change nothing. Once no unknown values remain, the boundary separates the two groups. Moving the pivot there gives the return index its meaning.

Turn one partition into a complete sort

Call Quicksort again on the left range and then the right range. Exclude index 3: its pivot is settled. Use the same rule inside each smaller range.

sort(0, 6) → pivot 5 at index 3
├── sort(0, 2) → pivot 3 at index 1
│   ├── sort(0, 0) → one value: return
│   └── sort(2, 2) → one value: return
└── sort(4, 6) → pivot 7 at index 4
    ├── sort(4, 3) → empty range: return
    └── sort(5, 6) → pivot 9 at index 6
        ├── sort(5, 5) → one value: return
        └── sort(7, 6) → empty range: return

Each box is a range of one shared array, not a new array. A range with zero or one value is already sorted. These are the stopping cases. Every other call removes its pivot from the next two ranges, so the tasks get smaller.

After both children finish, the parent range is sorted. No merge is needed: no value from the left side needs to cross the pivot, and no value from the right side needs to cross back.

The result is [2, 3, 4, 5, 7, 8, 9].

The working Python implementation

Bounds are inclusive: lo and hi both belong to the active range. Python’s range(lo, hi) stops before hi, leaving the pivot out of the scan.

def partition(a, lo, hi):
    pivot = a[hi]
    boundary = lo
    for scan in range(lo, hi):
        if a[scan] < pivot:
            a[boundary], a[scan] = a[scan], a[boundary]
            boundary += 1
    a[boundary], a[hi] = a[hi], a[boundary]
    return boundary


def quicksort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo >= hi:
        return
    p = partition(a, lo, hi)
    quicksort(a, lo, p - 1)
    quicksort(a, p + 1, hi)


numbers = [7, 2, 9, 4, 3, 8, 5]
quicksort(numbers)
print(numbers)  # [2, 3, 4, 5, 7, 8, 9]

Download the complete Python example, including both algorithms and independent example runs. It is the same learner source used for this lesson.

A swap can address the same slot twice. For example, a small value may already be at the boundary. The code still advances the boundary; it does not need to move a different value every time.

Reuse the guarantee: find one rank

Suppose we only want the third smallest value. Its target is index 2 in ascending order. After the first partition, pivot 5 is at index 3. The answer must be on the left. There is no reason to sort the right side.

Partition [2, 4, 3] around 3. Now 3 is at index 1. The target is to its right, leaving index 2 alone: 4 is the answer.

For the second largest, the ascending target is n − k = 7 − 2 = 5. Keep the right range after the first partition. Its later partitions lead to 8. The lab lets you switch between both tasks on the same input.

This is Quickselect. With a final-pivot partition, compare the returned pivot index with the target: keep the left range, keep the right range, or return the pivot value. Quicksort needs both sides; Quickselect needs at most one.

def quickselect(a, k, order="smallest"):
    if type(k) is not int or not 1 <= k <= len(a):
        raise ValueError("k must be an integer in 1..len(a).")
    if order not in ("smallest", "largest"):
        raise ValueError("order must be smallest or largest.")
    target = k - 1 if order == "smallest" else len(a) - k
    lo, hi = 0, len(a) - 1
    while lo < hi:
        p = partition(a, lo, hi)
        if p == target:
            return a[p]
        if target < p:
            hi = p - 1
        else:
            lo = p + 1
    return a[lo]



numbers = [7, 2, 9, 4, 3, 8, 5]
print(quickselect(numbers.copy(), 3))  # third smallest: 4
print(quickselect(numbers.copy(), 2, "largest"))  # second largest: 8

The function accepts a one-based rank k, then converts it once. Its internal target remains a global index while lo and hi move. We do not subtract the discarded count from it. The copies above let the two demonstrations start from the same input; the selection function itself rearranges its input in place.

Work, memory and the cases that change the story

A partition of m values makes m − 1 key comparisons. Our complete seven-value sort makes 11. This count describes the example, not a timing benchmark.

With reasonably balanced splits, Quicksort has logarithmic tree depth and O(n log n) work. Repeated extreme splits produce ranges of sizes n, n−1, n−2 and so on: quadratic work. The lab uses a fixed last pivot so you can reproduce every step. Already sorted distinct input exposes its worst case.

Randomized pivots give expected O(n log n) Quicksort time on distinct keys. That is an expectation over the random choices, not a promise that every split is balanced. This fixed-pivot teaching code does not make random choices.

Quickselect discards a branch each time. Under randomized pivots on distinct keys, its expected time is O(n); its worst case is O(n²). One branch does not mean O(log n) work, because partition must still scan the active values.

The recursion tree and the live call stack are different. When the left branch returns, its frame leaves the stack before the sibling runs. Only the current call and waiting ancestors are live. Straightforward recursive Quicksort uses O(log n) stack space with balanced splits and O(n) in the worst case. The example reaches four live sort calls, counting base-case calls; the lab labels this count explicitly. The iterative Quickselect above uses O(1) auxiliary algorithm storage. The browser’s saved teaching frames are extra demonstration data, not part of either algorithm’s storage bound.

Equal values still count

In [1, 2, 2, 4, 4], the second and third smallest values are both 2. Rank counts occurrences, not distinct values.

Our strict < rule leaves equal values in the “at least pivot” region. It remains correct, but on an all-equal input each partition settles only one position. Randomizing which equal value becomes the pivot does not fix that pattern. A three-way partition groups values below, equal to, and above the pivot, then skips the equal region. That is a different contract, not a one-character edit to this code.

Similarly, a canonical Hoare partition returns a separation boundary rather than necessarily fixing the pivot at its return index. Its recursive bounds differ. Do not combine one partition’s return value with another implementation’s recursive calls.

Check your understanding

• After the first partition, what is finished? Which two ranges remain unsorted?
• When 4 swaps with 7, why is it safe to leave the displaced 7 in the checked region?
• Why does sort(4, 3) return immediately?
• Which branch can the third-smallest search discard? Why does the second-largest search choose differently?
• When a branch returns, what disappears from the live stack but remains in the tree history?

Try the lab below before using the reversible “I understand this concept” control. Reading and stepping do not mark it for you.

Continue from here

Compare the order of work with Merge Sort: it splits first, then merges sorted pieces. For a different selection strategy, see binary heaps and Top K. Practice the rank idea with Kth Largest Element in an Array, or use the Quicksort learning path to see its connected concepts.

Sources and implementation boundaries

The explanation and example above are original. The technical distinctions were checked against Princeton’s Quicksort and Quickselect implementation, Temple’s partition contracts, Princeton’s three-way partition, and Cornell’s time and stack-space analysis. Princeton’s two-pointer partition differs from the single-scan teaching implementation here; each source’s bounds belong to its own contract.