Quick Sort — Partitioning Around a Pivot

Quick sort picks a pivot, partitions elements into < pivot, == pivot, > pivot (two-way or three-way), and recurses. Average O(n log n) with small constants; worst O(n²) on bad pivots—hence randomization or introspection in libraries.

Why this shows up in the real world

C++ std::sort often uses introsort (quicksort + heapsort safety net). Java Arrays.sort for primitives uses dual-pivot quicksort variants. Many standard library sorts choose quicksort family for in-place speed on random data. Understanding pivot strategies explains occasional catastrophic slowdowns on adversarial already-sorted arrays if pivot is naive.

Core idea (explained for students)

Choose pivot (first, middle, median-of-three, or random). Partition in linear time so pivot lands at final sorted index. Recurse on left and right subranges. Random pivot yields expected O(n log n) against adversarial inputs. Three-way partition (Dutch flag style) speeds up duplicate-heavy arrays.

Try this in Python

import random


def quicksort(a):
    if len(a) <= 1:
        return a
    pivot = random.choice(a)
    lows = [x for x in a if x < pivot]
    mids = [x for x in a if x == pivot]
    highs = [x for x in a if x > pivot]
    return quicksort(lows) + mids + quicksort(highs)


print(quicksort([3, 1, 4, 1, 5, 9, 2, 6]))

Common mistakes

• Stack overflow on skewed recursion—tail-call or sort smaller side first.
• Equal elements all going one side—degrades to O(n²).
• Off-by-one partition indices.

Key takeaways

• Great in-place average performance.
• Combine with random pivot or introsort for safety.
• Learn Lomuto vs Hoare partition variants.