Quick Sort

Quick Sort is a divide-and-conquer sorting algorithm that picks a “pivot” element, rearranges (“partitions”) the array so every element smaller than the pivot ends up to its left and every larger element ends up to its right, and then recursively sorts each side. It is one of the most widely used general-purpose sorts because it works in-place with very little extra memory, its inner loop is simple and cache-friendly, and on typical inputs it’s extremely fast. It’s also a favorite in coding interviews because implementing it correctly touches recursion, in-place array manipulation, and worst-case reasoning all at once.

Overview / How It Works

Imagine you have a stack of exam papers to sort by score. You grab one paper at random and call its score the pivot. You then make two piles: papers with a lower score go left, papers with a higher score go right (papers tied with the pivot can go in either pile, or their own middle pile). The pivot itself is now in its final sorted position — nothing smaller than it will ever move to its right, and nothing larger will ever move to its left. You then repeat the exact same process independently on the left pile and the right pile, and keep recursing until every pile has zero or one papers left, at which point everything is trivially sorted. Stitch the piles back together in order and the whole stack is sorted.

That splitting-and-recombining step is called partitioning, and it’s the heart of Quick Sort. A common in-place partitioning method is the Lomuto scheme: pick the last element of the current range as the pivot, then walk an index j across the range while a second index i tracks the boundary of “everything seen so far that is <= pivot.” Every time arr[j] is less than or equal to the pivot, you advance i and swap arr[i] with arr[j], growing the “small” region by one. After the walk finishes, you swap the pivot into position i + 1, which is exactly the boundary between the small and large regions — the pivot’s final sorted spot. Quick Sort then recurses on the sub-range left of the pivot and the sub-range right of it.

Unlike Merge Sort, Quick Sort does almost all of its work before the recursive calls (during partitioning) rather than after, and it can sort in-place, needing only O(log n) extra memory for the recursion itself rather than a second array. The tradeoff is that its performance depends heavily on how balanced the partitions turn out to be, which in turn depends on which element you choose as the pivot.

Time and Space Complexity

Partitioning a range of size k takes O(k) time, since it’s a single pass through the range. The total running time depends on how many “levels” of partitioning happen before every sub-range shrinks to size 0 or 1.

Case Time Complexity Why
Best case O(n log n) Every pivot splits its range into two roughly equal halves, giving log n levels of recursion, each doing O(n) total partition work
Average case O(n log n) With a reasonably chosen pivot (e.g. random or middle element), partitions are unbalanced sometimes but balanced enough on average that the recursion depth stays O(log n)
Worst case O(n2) The pivot is repeatedly the smallest or largest element in its range (e.g. an already-sorted array with a last-element pivot), so each partition only shrinks the range by one, giving n levels of O(n) work each

Space complexity for the in-place (Lomuto) version is O(log n) on average and O(n) in the worst case — that’s the depth of the call stack, since partitioning itself uses only a constant amount of extra memory. The simpler, non-in-place version shown in Example 1 below (built with list comprehensions) is easier to read but is not in-place: it allocates new lists at every level, using O(n) additional memory overall. One more important fact: Quick Sort is not stable. The swaps performed during partitioning can change the relative order of elements that compare as equal. If you need a stable sort, use Merge Sort, Insertion Sort, or Python’s built-in sorted()/list.sort(), which use Timsort (stable) rather than Quick Sort internally.

Examples

Example 1: A simple, easy-to-trace version

This version isn’t in-place, but it directly mirrors the “three piles” mental model and is the easiest way to see why Quick Sort works before worrying about in-place swapping.

def quicksort(arr: list[int]) -> list[int]:
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

numbers = [8, 3, 5, 4, 7, 6, 1, 2]
print(quicksort(numbers))

Output:

[1, 2, 3, 4, 5, 6, 7, 8]

Tracing it: with [8, 3, 5, 4, 7, 6, 1, 2], the middle index is 4, so the pivot is 7. Everything less than 7 ([3, 5, 4, 6, 1, 2]) goes left, [7] stays in the middle, and [8] goes right. The function then recurses on [3, 5, 4, 6, 1, 2], which picks pivot 6, splits into [3, 5, 4, 1, 2] and an empty right side, and so on — each recursive call shrinks the problem until every list has zero or one elements, and the pieces are concatenated back together already sorted.

Example 2: The classic in-place version (Lomuto partition)

This is the version most textbooks and interviews expect: it sorts the array in-place using only index arithmetic and swaps, needing no extra arrays.

def partition(arr: list[int], low: int, high: int) -> int:
    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_inplace(arr: list[int], low: int = 0, high: int | None = None) -> None:
    if high is None:
        high = len(arr) - 1
    if low < high:
        pivot_index = partition(arr, low, high)
        quicksort_inplace(arr, low, pivot_index - 1)
        quicksort_inplace(arr, pivot_index + 1, high)

numbers = [8, 3, 5, 4, 7, 6, 1, 2]
quicksort_inplace(numbers)
print(numbers)

Output:

[1, 2, 3, 4, 5, 6, 7, 8]

The default parameter high: int | None = None lets the first call omit high; the function fills it in as len(arr) - 1. Each call to partition picks the last element of the current range as the pivot and returns the index where it landed; quicksort_inplace then recurses on the two ranges to either side of that index, deliberately excluding the pivot itself since it’s already in its final position. The full step-by-step trace of this exact call is in the next section.

Example 3: A realistic variant — Quickselect

Quick Sort’s partition step has a famous side benefit: if you only need the k-th smallest (or largest) element rather than a fully sorted array, you don’t need to recurse into both sides — you can throw away the side that can’t contain your answer. This is Quickselect, and it’s a very common interview follow-up to Quick Sort.

def quickselect(arr: list[int], k: int) -> int:
    """Return the k-th smallest element (0-indexed)."""
    if len(arr) == 1:
        return arr[0]

    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    if k < len(left):
        return quickselect(left, k)
    elif k < len(left) + len(middle):
        return middle[0]
    else:
        return quickselect(right, k - len(left) - len(middle))

numbers = [8, 3, 5, 4, 7, 6, 1, 2]
third_smallest = quickselect(numbers, 2)
print(third_smallest)

Output:

3

Sorted, this array is [1, 2, 3, 4, 5, 6, 7, 8], so the element at index 2 (the 3rd smallest, 0-indexed) is 3 — which is exactly what quickselect returns, without ever fully sorting the array. Because each call only recurses into one side instead of two, Quickselect runs in O(n) average time, versus O(n log n) for sorting everything first.

How It Works Step by Step

Here is the full trace of quicksort_inplace from Example 2 on [8, 3, 5, 4, 7, 6, 1, 2]:

  1. partition(arr, 0, 7): pivot = arr[7] = 2. Scanning indices 0–6, only arr[6] = 1 is <= 2, so it’s swapped to index 0, giving [1, 3, 5, 4, 7, 6, 8, 2]. The pivot is then swapped into position 1: [1, 2, 5, 4, 7, 6, 8, 3]. The pivot 2 is now at its final index, 1.
  2. Recurse left on indices [0, 0] (a single element, already sorted) and right on indices [2, 7]: [5, 4, 7, 6, 8, 3].
  3. partition(arr, 2, 7): pivot = arr[7] = 3. None of 5, 4, 7, 6, 8 are <= 3, so the pivot swaps straight to index 2: [1, 2, 3, 4, 7, 6, 8, 5]. Pivot 3 lands at index 2.
  4. Recurse right on indices [3, 7]: [4, 7, 6, 8, 5]. partition(arr, 3, 7): pivot = arr[7] = 5. Only 4 is <= 5, so it stays put and the pivot swaps into index 4: [1, 2, 3, 4, 5, 6, 8, 7]. Pivot 5 lands at index 4.
  5. Recurse right on indices [5, 7]: [6, 8, 7]. partition(arr, 5, 7): pivot = arr[7] = 7. Only 6 is <= 7, so the pivot swaps into index 6: [1, 2, 3, 4, 5, 6, 7, 8]. Pivot 7 lands at index 6.
  6. The remaining ranges are all size 0 or 1, so recursion bottoms out. The final array is [1, 2, 3, 4, 5, 6, 7, 8] — fully sorted, in-place, with no extra array ever allocated.

Common Mistakes

Mistake 1: Always picking a fixed pivot position

It’s tempting to always use the first (or last) element as the pivot, since it’s the simplest to code:

def partition_naive(arr: list[int], low: int, high: int) -> int:
    pivot = arr[low]
    i = low + 1
    for j in range(low + 1, high + 1):
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[low], arr[i - 1] = arr[i - 1], arr[low]
    return i - 1

This compiles and runs fine, but on an already-sorted array (very common in real data, e.g. re-sorting a log file), the first element is always the smallest remaining value, so every partition puts zero elements on one side and everything else on the other. That degrades Quick Sort to its O(n2) worst case, and because recursion depth also becomes O(n), a large enough sorted input can hit Python’s recursion limit (around 1000 by default) and raise a RecursionError.

The fix is to avoid a fixed, predictable pivot position — pick a random index, or use “median-of-three” (compare the first, middle, and last elements and use the median of those), then swap it into position before partitioning:

import random

def partition_randomized(arr: list[int], low: int, high: int) -> int:
    random_index = random.randint(low, high)
    arr[random_index], arr[high] = arr[high], arr[random_index]
    return partition(arr, low, high)

Randomizing the pivot doesn’t change the worst case in theory, but it makes that worst case astronomically unlikely for any specific input an adversary (or unlucky dataset) could hand you, since the bad case would require an unlikely sequence of random choices rather than a common data pattern like “already sorted.”

Mistake 2: An off-by-one that re-includes the pivot

After partition places the pivot at its final index, the recursive calls must exclude that index — it’s already sorted and must never be touched again. It’s an easy slip to recurse on pivot_index instead of pivot_index - 1:

def quicksort_inplace(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        pivot_index = partition(arr, low, high)
        quicksort_inplace(arr, low, pivot_index)  # BUG: still includes the pivot
        quicksort_inplace(arr, pivot_index + 1, high)

On most inputs this just wastes a little time reprocessing one extra element. But on an already-sorted array, the pivot (the last element, which is the maximum of its range) never moves during partitioning — it stays at index high. That means pivot_index equals high, and the buggy left call becomes quicksort_inplace(arr, low, high): the exact same range as the call that’s currently running. That’s unbounded recursion on the same arguments, which will run until Python’s recursion limit is hit and raises RecursionError, rather than simply being slow. The fix is the one shown in Example 2: always recurse on pivot_index - 1 for the left half, explicitly excluding the pivot:

def quicksort_inplace_fixed(arr: list[int], low: int = 0, high: int | None = None) -> None:
    if high is None:
        high = len(arr) - 1
    if low < high:
        pivot_index = partition(arr, low, high)
        quicksort_inplace_fixed(arr, low, pivot_index - 1)
        quicksort_inplace_fixed(arr, pivot_index + 1, high)

The general lesson: whenever a partition-style algorithm returns a boundary index, double-check whether that index itself belongs in the next recursive call or must be excluded — getting it wrong doesn’t always crash loudly, and can silently turn into much worse performance or, as here, genuine infinite recursion on specific inputs.

Best Practices

  • For real production code, just use Python’s built-in sorted() or list.sort() — they use Timsort, which is stable, has a guaranteed O(n log n) worst case, and is implemented in C. Hand-rolled Quick Sort is for learning the technique and for interviews, not for replacing the standard library.
  • Randomize the pivot (or use median-of-three) any time input data might already be sorted, reverse-sorted, or otherwise adversarial — this is what protects average-case performance in practice.
  • Prefer the in-place, index-based partitioning version (Example 2) over the list-comprehension version (Example 1) when memory matters; the comprehension version is easier to read but allocates new lists at every level.
  • For very large inputs, consider an iterative version using an explicit stack instead of recursion, to sidestep Python’s recursion limit entirely in worst-case scenarios.
  • When you only need the k-th smallest/largest element rather than a full ordering, reach for Quickselect instead of sorting the whole array — it’s O(n) average versus O(n log n).
  • Never rely on Quick Sort to preserve the relative order of equal elements; if that matters (e.g. sorting by score but wanting ties to keep their original submission order), use a stable sort like Merge Sort or sorted() instead.
  • Avoid mutable default arguments (like def f(arr, acc=[])) in any recursive helper you add on top of these examples — the default list is created once and shared across every call, silently accumulating stale data. Use None as the default and initialize inside the function, exactly as high: int | None = None does above.

Practice Exercises

  • Implement Quick Sort using the Hoare partition scheme instead of Lomuto: use two indices starting at each end of the range, moving them toward each other and swapping when they find a pair of out-of-place elements. Note that Hoare’s scheme returns a different kind of split point than Lomuto’s, so the recursive calls look slightly different.
  • Given the array [7, 2, 9, 4, 1, 5, 3], use Quickselect to find the 4th smallest element (0-indexed, k = 3) without fully sorting the array. (Hint: sort it by hand first to check your answer — the fully sorted array is [1, 2, 3, 4, 5, 7, 9].)
  • Add a counter to the in-place Quick Sort from Example 2 that counts how many swaps partition performs. Run it on a random array, an already-sorted array, and a reverse-sorted array of the same size, and compare the swap counts. Does the pattern match the best/average/worst-case analysis above?

Summary

  • Quick Sort is a divide-and-conquer algorithm: pick a pivot, partition the array around it so smaller elements land left and larger elements land right, then recursively sort each side.
  • Best and average time complexity is O(n log n); worst case is O(n2), which happens when the pivot is repeatedly the smallest or largest remaining element (classically, a sorted array with a fixed last-element pivot).
  • Space complexity is O(log n) on average for the in-place version (recursion stack only), up to O(n) in the worst case; the simpler list-comprehension version trades in-place-ness for O(n) extra memory.
  • Quick Sort is not stable — use Merge Sort or Python’s built-in Timsort-based sorted() when relative order of equal elements must be preserved.
  • Randomized or median-of-three pivot selection defends against the O(n2) worst case on sorted or adversarial input.
  • Quickselect, built on the same partition step, finds the k-th smallest/largest element in average O(n) time without sorting the whole array.