What Is a Partition in Quicksort? The Step That Makes It Work

Most explanations of quicksort jump straight to the recursion diagram. Left half, right half, divide and conquer, everyone nods along. What they quietly skip is the single operation that makes all of that possible: the partition step.

Partition is not quicksort. Quicksort is nothing without it. And if you can't explain what partition actually does, you're one interviewer question away from discovering that.

One Element, Permanently Placed (and Very Smug About It)

You have an array. You pick one element and call it the pivot. Partition rearranges the array in place so that:

Every element smaller than the pivot is to its left.
Every element larger than the pivot is to its right.
The pivot ends up at its correct final position.

That third point is the key insight. After one call to partition, the pivot is permanently placed. You never touch it again, no matter how chaotic the rest of the array looks. Quicksort recursively handles the left and right sides, but the pivot is done. Retired. Out of the game.

The Quicksort Partition: Traced on a Real Array

Take this array:

[5, 3, 8, 1, 9, 2]

Pick 2 as the pivot (the last element, which is what the Lomuto scheme does by default).

Goal: rearrange so everything less than 2 sits left of it, everything greater sits right.

Walk through each element left to right:

5 > 2, skip
3 > 2, skip
8 > 2, skip
1 ≤ 2, move it into the "left zone"
9 > 2, skip

Then place the pivot between the two zones.

Result:

[1, 2, 8, 5, 9, 3]
    ^
  pivot at index 1, final sorted position

Left of index 1: [1], all ≤ 2. Right of index 1: [8, 5, 9, 3], all > 2. The pivot 2 sits at index 1, exactly where it belongs in the fully sorted array [1, 2, 3, 5, 8, 9].

One pass. Done. The pivot will never be disturbed again.

Lomuto: The Scheme You'll Actually Write Under Pressure

The approach above is Lomuto. Easier to implement and reason about, so most courses teach it first. Easier to mess up too, but at least when you mess it up, it's obvious why.

The idea: maintain a boundary pointer i that tracks where the "less than pivot" region ends. Walk a second pointer j through the array. Whenever arr[j] is ≤ pivot, extend the left region by one and swap arr[j] into it.

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1  # right edge of the "less than" zone

    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

Traced on arr = [5, 3, 8, 1, 9, 2], low = 0, high = 5:

j	arr[j]	≤ pivot?	i	array state
0	5	no	-1	[5, 3, 8, 1, 9, 2]
1	3	no	-1	[5, 3, 8, 1, 9, 2]
2	8	no	-1	[5, 3, 8, 1, 9, 2]
3	1	yes	0	[1, 3, 8, 5, 9, 2]
4	9	no	0	[1, 3, 8, 5, 9, 2]

After the loop: swap arr[i+1] = arr[1] with arr[high] = arr[5].

Final: [1, 2, 8, 5, 9, 3]. Pivot index returned: 1.

Lomuto partition traced step by step: pivot 2 moves to index 1, its final sorted position

Every element is visited exactly once, so partition runs in O(n) time and O(1) extra space. That holds regardless of what the array looks like going in.

Hoare: Faster, Trickier, and a Source of Infinite Suffering

Tony Hoare introduced a different scheme when he invented quicksort in 1959. Two pointers start at opposite ends and march toward each other, swapping elements on the wrong side.

def partition_hoare(arr, low, high):
    pivot = arr[low]
    i = low - 1
    j = high + 1

    while True:
        i += 1
        while arr[i] < pivot:
            i += 1
        j -= 1
        while arr[j] > pivot:
            j -= 1
        if i >= j:
            return j
        arr[i], arr[j] = arr[j], arr[i]

Hoare's scheme does about three times fewer swaps on average and handles duplicates more gracefully. The catch: the pivot does not necessarily land at the returned index. The index j just marks where the two zones split. This surprises most developers the first time they see it, and it leads to off-by-one bugs that feel personally insulting when you finally find them.

For interviews, Lomuto is usually the right call. Reach for Hoare only if you specifically need it, or if you enjoy pain.

Pivot Choice Is the Whole Game

Partition itself is always O(n). What determines quicksort's overall complexity is how many times partition gets called, which depends entirely on whether each pivot splits the array roughly in half.

Best case: balanced splits every time. O(log n) levels of recursion, O(n) work per level = O(n log n) total.

Worst case: the pivot is always the minimum or maximum element. Each partition produces a subarray of size n-1 and one of size 0. That means O(n) levels, O(n) work each = O(n²) total.

This worst case is not theoretical. It hits naturally when you always pick the last element as pivot and the input is already sorted. Your "sort this array" function receives a sorted array, produces O(n²) work, and you've made things dramatically worse than if you'd done nothing. Classic.

The standard fix is random pivot selection:

import random

def partition_random(arr, low, high):
    pivot_idx = random.randint(low, high)
    arr[pivot_idx], arr[high] = arr[high], arr[pivot_idx]
    return partition(arr, low, high)  # Lomuto from above

Swap a random element into the last position, then run Lomuto normally. Every possible pivot is equally likely, and the expected number of levels drops to O(log n) regardless of input order.

Quicksort in Three Lines

Once you have partition, quicksort writes itself:

def quicksort(arr, low, high):
    if low < high:
        pi = partition_random(arr, low, high)
        quicksort(arr, low, pi - 1)
        quicksort(arr, pi + 1, high)

The recursion only works inward because the pivot is already placed. Call quicksort(arr, 0, len(arr) - 1) to sort the full array.

Why Interviews Keep Coming Back to Partition

Quickselect: the kth element in O(n)

Partition tells you the pivot's exact rank in the sorted order. If partition returns index k-1, you just found the kth smallest element without sorting anything else. No sorting required. You did less work and got a better result.

This is the basis of Quickselect. After one partition call, either:

The pivot is at position k. Done.
The pivot is left of k. Recurse only on the right side.
The pivot is right of k. Recurse only on the left side.

Average case is O(n). LeetCode 215 (Kth Largest Element) and nearly every "find the kth element" problem have an O(n) solution that uses exactly this idea. Most candidates sort the array and call it a day.

The Dutch National Flag problem

Dijkstra's three-way partition extends the concept to three zones: less than, equal to, greater than. It is the core of the Dutch National Flag problem, which maps directly to LeetCode 75 (Sort Colors).

Whenever you see a problem asking you to partition an array into exactly three groups in a single pass, you are looking at a partition variant.

Recognizing Partition in Disguise

Partition problems often do not announce themselves. They say:

"Rearrange so all negative numbers come before positives."
"Move all zeros to the end without changing relative order of non-zeros."
"Separate even and odd numbers in-place."

These are all partition. The structure is identical: maintain a boundary, walk a pointer, swap elements that belong on the other side. Recognizing that structure is what separates a 20-minute solution from a 45-minute struggle where you reinvent partition from scratch without realizing it.

If you want to practice catching the pattern under actual interview conditions, SpaceComplexity runs voice-based mock interviews with rubric scoring, so you find out whether you recognize the partition signal before the interviewer has to hint.

Complexity

Scenario	Time	Recursion stack space
Best / average case	O(n log n)	O(log n)
Worst case (bad pivot)	O(n²)	O(n)
Partition itself	O(n)	O(1)

The stack depth comes from the recursive calls, not from partition. Sorting the smaller subarray first caps the stack at O(log n) even in pathological cases.