Quicksort is the sort most language standard libraries reach for first (with a merge-sort or insertion-sort fallback for edge cases). It sorts in place, has tiny constant overhead, and averages $O(n \log n)$ — but unlike merge sort, its worst case is a real $O(n^2)$ that shows up on ordinary-looking input if you’re not careful about pivot choice.

What you’ll learn

• Partitioning — the one operation quicksort is built from — via the Lomuto scheme, plus a look at the alternative Hoare scheme.
• Recursive, in-place quicksort.
• Why picking the last element as pivot turns an already-sorted array into the $O(n^2)$ worst case.
• The randomized pivot fix, and why it makes the worst case vanishingly unlikely in practice.
• Why quicksort is not stable, and when that matters.

Partitioning: the Lomuto scheme

Partitioning rearranges a subarray around a chosen pivot value so that everything $\le$ the pivot ends up to its left, everything greater ends up to its right, and the pivot lands in its final, correctly-sorted position. Everything else in quicksort is just “partition, then recurse on both halves.”

The Lomuto scheme picks the last element as the pivot and walks the array with two indices: jj scans left to right, ii tracks the boundary of the “elements seen so far that are $\le$ pivot” region.

def partition(arr, low, high):
    pivot = arr[high]          # last element as pivot
    i = low - 1                # boundary of the "<= pivot" region
 
    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]   # drop pivot into place
    return i + 1                                     # pivot's final index
 
 
arr = [8, 3, 1, 7, 0, 2]
p = partition(arr, 0, len(arr) - 1)
print("after one partition:", arr)
print("pivot landed at index:", p)

def partition(arr, low, high):
    pivot = arr[high]          # last element as pivot
    i = low - 1                # boundary of the "<= pivot" region
 
    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]   # drop pivot into place
    return i + 1                                     # pivot's final index
 
 
arr = [8, 3, 1, 7, 0, 2]
p = partition(arr, 0, len(arr) - 1)
print("after one partition:", arr)
print("pivot landed at index:", p)

Run it: everything left of the returned index is $\le 2$, everything right of it is $> 2$ — the pivot itself sits between them, already in its correct sorted spot. That’s the whole trick, repeated recursively.

Recursive quicksort, in place

Quicksort partitions the whole array, then recursively quicksorts the left and right sides of the pivot. There’s no merge step (unlike merge sort) — once both sides are sorted, the whole array is sorted, because partitioning already guaranteed the pivot’s position relative to everything else.

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
 
 
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)      # everything <= pivot
        quicksort(arr, p + 1, high)     # everything > pivot
    return arr
 
 
nums = [8, 3, 1, 7, 0, 10, 2, 5]
print("sorted:", quicksort(nums))

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
 
 
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)      # everything <= pivot
        quicksort(arr, p + 1, high)     # everything > pivot
    return arr
 
 
nums = [8, 3, 1, 7, 0, 10, 2, 5]
print("sorted:", quicksort(nums))

No extra array is allocated — every swap happens directly inside arrarr. Only the recursion’s call stack uses extra space.

Watch a single partition step by step

Why pivot choice matters: the O(n^2) trap

Lomuto’s partition always picks the last element as pivot. If the input is already sorted (or reverse-sorted), that pivot is always the largest (or smallest) remaining value — partitioning splits the array into a piece of size 00 and a piece of size n - 1n - 1, every single time.

def partition(arr, low, high, counter):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        counter[0] += 1   # count comparisons
        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
 
 
def quicksort(arr, low, high, counter):
    if low < high:
        p = partition(arr, low, high, counter)
        quicksort(arr, low, p - 1, counter)
        quicksort(arr, p + 1, high, counter)
 
 
sorted_input = list(range(200))       # already sorted -- the worst case
counter = [0]
quicksort(sorted_input, 0, len(sorted_input) - 1, counter)
print(f"n=200, already sorted: {counter[0]} comparisons")
print(f"n^2 would be {200 * 200}, n*log2(n) would be about {int(200 * 7.6)}")

def partition(arr, low, high, counter):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        counter[0] += 1   # count comparisons
        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
 
 
def quicksort(arr, low, high, counter):
    if low < high:
        p = partition(arr, low, high, counter)
        quicksort(arr, low, p - 1, counter)
        quicksort(arr, p + 1, high, counter)
 
 
sorted_input = list(range(200))       # already sorted -- the worst case
counter = [0]
quicksort(sorted_input, 0, len(sorted_input) - 1, counter)
print(f"n=200, already sorted: {counter[0]} comparisons")
print(f"n^2 would be {200 * 200}, n*log2(n) would be about {int(200 * 7.6)}")

That comparison count lands right on $n(n-1)/2$ — quadratic, not log-linear. Recursing into a 00-and-(n-1)(n-1) split at every level also means the recursion goes nn levels deep instead of $\log n$, which on a truly pathological input can blow the call stack too.

The fix: pick the pivot randomly

The failure mode above only happens because the pivot is picked by a fixed rule (always “last element”) that an input can be crafted to defeat. Picking the pivot uniformly at random before partitioning breaks that: no fixed input can reliably trigger the bad split anymore, because the “unlucky” pivot is a different, unpredictable index every run.

import random
 
 
def partition(arr, low, high):
    # swap a random element into the pivot slot before partitioning as usual
    rand_idx = random.randint(low, high)
    arr[rand_idx], arr[high] = arr[high], arr[rand_idx]
 
    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
 
 
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
 
 
already_sorted = list(range(15))
print("random-pivot quicksort:", quicksort(already_sorted))

import random
 
 
def partition(arr, low, high):
    # swap a random element into the pivot slot before partitioning as usual
    rand_idx = random.randint(low, high)
    arr[rand_idx], arr[high] = arr[high], arr[rand_idx]
 
    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
 
 
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
 
 
already_sorted = list(range(15))
print("random-pivot quicksort:", quicksort(already_sorted))

The worst case is still technically $O(n^2)$ — an adversary who can see your random seed could still construct a bad case — but for any fixed input, the expected running time is $O(n \log n)$. This is the standard production fix; some libraries instead pick the median of three (first, middle, last elements) as a cheaper, deterministic-ish alternative.

Time and space complexity

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 2161 — Partition Array According to Given Pivot · Medium

Problem. Rearrange numsnums so that every value less than pivotpivot comes first, then every value equal to pivotpivot, then every value greater — and the relative order within the less-than and greater-than groups must be preserved.

Constraints. 1 <= len(nums) <= 10^51 <= len(nums) <= 10^5, -10^6 <= nums[i] <= 10^6-10^6 <= nums[i] <= 10^6, and pivotpivot occurs in numsnums.

Examples. nums = [9,12,5,10,14,3,10], pivot = 10nums = [9,12,5,10,14,3,10], pivot = 10 gives [9,5,3,10,10,12,14][9,5,3,10,10,12,14] · nums = [-3,4,3,2], pivot = 2nums = [-3,4,3,2], pivot = 2 gives [-3,2,4,3][-3,2,4,3]

LC 462 — Minimum Moves to Equal Array Elements II · Medium

Problem. In one move you may increment or decrement any element by 1. Return the minimum number of moves to make all elements equal.

Constraints. 1 <= len(nums) <= 10^51 <= len(nums) <= 10^5, -10^9 <= nums[i] <= 10^9-10^9 <= nums[i] <= 10^9.

Examples. [1,2,3][1,2,3] gives 22 · [1,10,2,9][1,10,2,9] gives 1616

LC 969 — Pancake Sorting · Medium

Problem. You may only reverse a prefix of the array (a “flip”). Return any sequence of flip sizes that sorts the array, using at most 10 * len(arr)10 * len(arr) flips.

Constraints. 1 <= len(arr) <= 1001 <= len(arr) <= 100, arrarr is a permutation of 1..len(arr)1..len(arr).

Examples. [3,2,4,1][3,2,4,1] gives a valid flip sequence such as [4,2,4,3][4,2,4,3] · [1,2,3][1,2,3] gives [][]

Recap

• Quicksort = partition around a pivot, then recurse on both sides — no merge step needed.
• The Lomuto scheme picks the last element as pivot and tracks a growing ”$\le$ pivot” region with index ii; Hoare’s two-pointer scheme does fewer swaps but returns a split point, not the pivot’s final index.
• Fixed pivot choice (always last element) degrades to $O(n^2)$ on sorted or reverse-sorted input — the exact input you’d expect to see often.
• A randomized (or median-of-three) pivot makes that worst case practically unreachable, restoring the expected $O(n \log n)$.
• In-place, $O(\log n)$ average extra space, not stable.

Next: Heap Sort — a comparison sort with a guaranteed $O(n \log n)$ worst case, no randomization required, built directly on the binary heap from Phase 3.