147. Quicksort Partition

Why this mechanism works

Move a randomly selected pivot to the final cell of the current range. A write frontier separates values <=pivot from larger values while scanning the rest. The final pivot swap places it between those regions, after which recursive calls exclude its fixed position. Random pivots reduce consistent imbalance on distinct data, but do not solve the all-equal case for this partition.

State and boundaries

During partition, [left,write) is <=pivot and [write,i) is >pivot. After the final swap, write is the pivot's final index.

Protocol

1. Stop ranges of length<=1.
2. Choose and move a pivot to right-1.
3. Scan and compact <=pivot values before write.
4. Swap the pivot into write.
5. Recurse on [left,write) and [write+1,right).

Visualization

[ <= pivot | > pivot | pivot ]
            write       right-1
final swap fixes pivot at write
recurse on the two sides only

Python implementation

import random

def quick_sort(nums):
    def sort(left, right):
        if right - left <= 1:
            return
        chosen = random.randrange(left, right)
        nums[chosen], nums[right - 1] = nums[right - 1], nums[chosen]
        pivot = nums[right - 1]
        write = left
        for i in range(left, right - 1):
            if nums[i] <= pivot:
                nums[write], nums[i] = nums[i], nums[write]
                write += 1
        nums[write], nums[right - 1] = nums[right - 1], nums[write]
        sort(left, write)
        sort(write + 1, right)
    sort(0, len(nums))
    return nums

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 quick_sort: def sort(left, right):
nums=[4, 1, 3, 2]

L5 sort: if right - left <= 1:
left=0; right=4; nums=[4, 1, 3, 2]

L7 sort: chosen = random.randrange(left, right)
left=0; right=4; nums=[4, 1, 3, 2]; chosen=0

L8 sort: nums[chosen], nums[right - 1] = nums[right - 1], nums[chosen]
left=0; right=4; nums=[2, 1, 3, 4]; chosen=0

L9 sort: pivot = nums[right - 1]
left=0; right=4; nums=[2, 1, 3, 4]; chosen=0; pivot=4

L10 sort: write = left
left=0; right=4; nums=[2, 1, 3, 4]; chosen=0; pivot=4; write=0

L11 sort: for i in range(left, right - 1):
left=0; right=4; nums=[2, 1, 3, 4]; chosen=0; pivot=4; write=0; i=0

L14 sort: write += 1
left=0; right=4; nums=[2, 1, 3, 4]; chosen=0; pivot=4; write=1; i=0

... 15 intermediate state changes omitted ...

L5 sort: if right - left <= 1:
left=2; right=3; nums=[1, 2, 3, 4]

L16 sort: sort(left, write)
left=0; right=4; nums=[1, 2, 3, 4]; chosen=0; pivot=4; write=3; i=2

L5 sort: if right - left <= 1:
left=4; right=4; nums=[1, 2, 3, 4]

L18 quick_sort: sort(0, len(nums))
nums=[1, 2, 3, 4]

L4 quick_sort: def sort(left, right):
nums=[2, 2, 2]

L5 sort: if right - left <= 1:
left=0; right=3; nums=[2, 2, 2]

L7 sort: chosen = random.randrange(left, right)
left=0; right=3; nums=[2, 2, 2]; chosen=2

L9 sort: pivot = nums[right - 1]
left=0; right=3; nums=[2, 2, 2]; chosen=2; pivot=2

L10 sort: write = left
left=0; right=3; nums=[2, 2, 2]; chosen=2; pivot=2; write=0

L11 sort: for i in range(left, right - 1):
left=0; right=3; nums=[2, 2, 2]; chosen=2; pivot=2; write=0; i=0

L14 sort: write += 1
left=0; right=3; nums=[2, 2, 2]; chosen=2; pivot=2; write=1; i=0

L11 sort: for i in range(left, right - 1):
left=0; right=3; nums=[2, 2, 2]; chosen=2; pivot=2; write=1; i=1

... 6 intermediate state changes omitted ...

L14 sort: write += 1
left=0; right=2; nums=[2, 2, 2]; chosen=0; pivot=2; write=1; i=0

L5 sort: if right - left <= 1:
left=0; right=1; nums=[2, 2, 2]

L5 sort: if right - left <= 1:
left=2; right=2; nums=[2, 2, 2]

L5 sort: if right - left <= 1:
left=3; right=3; nums=[2, 2, 2]

Why the solution is correct

The partition loop preserves its two classified regions, and the final swap leaves every left value <=pivot and every right value >pivot. Recursive sorting of these disjoint regions therefore sorts the whole range while the pivot stays fixed. Each child range is strictly smaller.

Time and space

Expected O(n log n) time on distinct values with random pivots; O(n^2) worst case, including all-equal values here. Expected O(log n), worst O(n) call depth; no second array is allocated.

Common mistakes

Including the pivot again in a recursive child can prevent progress. Storing only a pivot index while swapping cells can accidentally change which value is the pivot.

Reasoning card

Transfer exercise

Replace the two-way partition with a three-way less/equal/greater partition and skip the entire equal region in recursion.