Quick Sort

The Pivot Game

You're organizing a massive deck of cards — say, 52 of them. You grab one card at random: the 7 of clubs. You declare it the pivot.

Now you go through the rest of the deck and create two piles: everything smaller than 7 goes left, everything larger goes right. The 7 sits in its final position — between the two piles. You know, with certainty, that it belongs exactly there.

Now you've reduced the problem: sort the left pile (all cards smaller than 7) and sort the right pile (all cards larger than 7). Repeat the same strategy on each pile. Pick a pivot, partition, recurse.

Eventually, every pile has one card. A one-card pile is sorted. Combine them all: sorted deck.

This is Quicksort — and it's why most real-world sort implementations are fast.

Why Quicksort Is Significant

Quicksort was invented by Tony Hoare in 1959. Despite being over 60 years old, it remains the algorithm of choice for general-purpose sorting in most standard libraries:

• C's qsort() — quicksort-based
• C++'s std::sort() — introspective sort (quicksort + heapsort fallback)
• Java's Arrays.sort() for primitive types — dual-pivot quicksort

The reason: cache efficiency. Quicksort sorts in-place and accesses memory in patterns that modern CPU caches handle extremely well.

The Core Operation: Partitioning

Partitioning is the step that places the pivot in its correct position and splits the array into two regions. Every element to the left of the pivot is smaller; every element to the right is larger.

Visual partition on [3, 6, 8, 10, 1, 2, 1] with pivot = 1 (last element):

Array: [3, 6, 8, 10, 1, 2, 1]
                            ^  pivot = 1
i = -1  (boundary of "less than pivot" region)

j=0: arr[0]=3 > 1 → no swap,  i stays -1
j=1: arr[1]=6 > 1 → no swap,  i stays -1
j=2: arr[2]=8 > 1 → no swap,  i stays -1
j=3: arr[3]=10 > 1 → no swap, i stays -1
j=4: arr[4]=1 ≤ 1 → swap arr[0] and arr[4], i=0
     Array: [1, 6, 8, 10, 3, 2, 1]
j=5: arr[5]=2 > 1 → no swap,  i stays 0

End: swap arr[i+1]=arr[1] with pivot arr[6]
     Array: [1, 1, 8, 10, 3, 2, 6]
Pivot index: 1

Left of index 1: [1]        → all ≤ 1 ✓
Right of index 1: [8,10,3,2,6] → all ≥ 1 ✓

Lomuto vs. Hoare Partition Schemes

Lomuto is taught first because the code is easier to understand. Hoare is often used in production.

Complete Implementation (Lomuto Partition)

def quick_sort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1   # initialize high on first call

    if low < high:            # base case: subarray of size 0 or 1
        pivot_idx = partition(arr, low, high)   # place pivot correctly
        quick_sort(arr, low, pivot_idx - 1)     # sort left of pivot
        quick_sort(arr, pivot_idx + 1, high)    # sort right of pivot


def partition(arr, low, high):
    pivot = arr[high]         # choose last element as pivot
    i = low - 1              # i tracks boundary of "less than pivot" region

    for j in range(low, high):
        if arr[j] <= pivot:   # current element belongs in left region
            i += 1
            arr[i], arr[j] = arr[j], arr[i]   # expand left region

    # Place pivot at its correct position (one past end of left region)
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1             # return pivot's final index


# Test
arr = [10, 7, 8, 9, 1, 5]
print("Input: ", arr)
quick_sort(arr)
print("Output:", arr)

Output:

Input:  [10, 7, 8, 9, 1, 5]
Output: [1, 5, 7, 8, 9, 10]

Traced recursion for [10, 7, 8, 9, 1, 5]:

quick_sort([10, 7, 8, 9, 1, 5], 0, 5)
  partition → pivot=5 at index 1: [1, 5, 8, 9, 7, 10]
  quick_sort([1], 0, 0)          → already sorted
  quick_sort([8, 9, 7, 10], 2, 5)
    partition → pivot=10 at index 5: [8, 9, 7, 10]
    quick_sort([8, 9, 7], 2, 4)
      partition → pivot=7 at index 2: [7, 9, 8]  ... → [7, 8, 9]
    quick_sort([], 6, 5)         → base case, skip
Final: [1, 5, 7, 8, 9, 10]

Pivot Selection Strategies

The pivot choice dramatically affects performance:

Median-of-three: Look at the first, middle, and last elements. Pick the median value as the pivot.

def median_of_three(arr, low, high):
    mid = (low + high) // 2
    candidates = [(arr[low], low), (arr[mid], mid), (arr[high], high)]
    candidates.sort()             # sort the three candidates
    return candidates[1][1]       # return index of median value

# With median-of-three, already-sorted input gets ideal pivots
# every time → consistently O(n log n) in practice

Complexity Analysis

Why worst case is O(n²):

Sorted input [1,2,3,4,5], pivot = last element:
Partition: pivot=5, left=[1,2,3,4], right=[]  → split: n-1 and 0
Partition: pivot=4, left=[1,2,3], right=[]    → split: n-2 and 0
Partition: pivot=3, left=[1,2], right=[]      → ...

Each partition only removes the pivot (1 element) — the recursion tree degrades to height n, with O(n) work per level → O(n²) total.

Why average case is O(n log n): Even if the pivot creates a 9:1 split (not ideal), the recursion depth is still O(log n). As long as splits aren't catastrophically uneven, performance remains logarithmic.

Quicksort vs. Merge Sort: Why Quicksort Often Wins in Practice

Despite merge sort's guaranteed O(n log n), quicksort is typically faster in practice:

The inner loop of quicksort's partition is extremely tight — just comparisons and swaps within the same array. This is exactly the kind of pattern modern CPU caches and branch predictors are optimized for.

A rough empirical rule: quicksort is 2–3x faster than merge sort on typical in-memory data despite the same asymptotic complexity.

Randomized Quicksort: Defeating the Worst Case

import random

def randomized_quick_sort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        # Randomly select pivot and swap to end before partitioning
        rand_idx = random.randint(low, high)
        arr[rand_idx], arr[high] = arr[high], arr[rand_idx]
        pivot_idx = partition(arr, low, high)
        randomized_quick_sort(arr, low, pivot_idx - 1)
        randomized_quick_sort(arr, pivot_idx + 1, high)

With random pivot selection, no input can consistently trigger the worst case. The expected running time is O(n log n) regardless of input order, and the probability of hitting O(n²) is astronomically small.

This is why competitive programmers and interviewers use shuffled input or randomized pivot when quicksort is required.

Key Takeaways

• Quicksort picks a pivot, partitions elements into smaller-left / larger-right, then recurses on each side
• O(n log n) average case, O(n²) worst case — worst case occurs on sorted input with a bad pivot strategy
• In-place (O(log n) space) — no auxiliary arrays needed, unlike merge sort
• Typically faster than merge sort in practice due to cache efficiency and low memory overhead
• Pivot selection is critical — random or median-of-three eliminates the practical risk of O(n²)
• Not stable — equal elements may change relative order during partitioning
• Used in: C's qsort, C++'s std::sort, Java's Arrays.sort for primitives, many more

Next lesson: The Sorting Comparison Guide — bringing together everything you've learned to pick the right algorithm for any situation.