Quicksort, Partitioning & the Dutch National Flag

Why quicksort deserves its own subtopic

Quicksort is the algorithm most likely to actually come up as a "implement this from scratch" interview question, because unlike merge sort it has a genuinely tricky decision point (how do you partition?) and a genuinely interesting failure mode (how does the "obviously O(n log n)" algorithm degrade to O(n²), and how do you defend against it?). You already met quicksort's partition step and its single-recursion cousin, quickselect, in the Heaps & Priority Queues topic as the way to find the Kth largest element in expected O(n) — this subtopic is the deeper dive into partitioning itself, and the classic three-way variant that handles duplicate-heavy arrays cleanly.

The algorithm, and the two classic partition schemes

Quicksort picks a pivot, partitions the array so everything less than the pivot ends up on its left and everything greater ends up on its right, then recurses on both sides:

def quicksort(arr, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    if lo < hi:
        p = _partition(arr, lo, hi)
        quicksort(arr, lo, p - 1)
        quicksort(arr, p + 1, hi)

Lomuto partition scheme (used in the Heaps topic's quickselect — one pointer, easy to reason about, slightly more swaps in practice):

def _partition_lomuto(arr, lo, hi):
    pivot = arr[hi]
    store = lo
    for i in range(lo, hi):
        if arr[i] < pivot:
            arr[i], arr[store] = arr[store], arr[i]
            store += 1
    arr[store], arr[hi] = arr[hi], arr[store]
    return store

Hoare partition scheme (two pointers converging from both ends — fewer swaps on average, the historically original version):

def _partition_hoare(arr, lo, hi):
    pivot = arr[(lo + hi) // 2]
    i, j = lo - 1, hi + 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]

Both are correct, O(n) per partition call, and O(1) extra space. Lomuto is easier to get right under interview pressure and is what most candidates should default to; Hoare is worth recognizing by name since it's what many textbooks and reference implementations actually use.

Why the worst case is O(n²), and why randomization is the fix

If the pivot is always the smallest or largest element in its subarray (which happens on already-sorted or reverse-sorted input if you naively always pick the first or last element as pivot), the partition splits the array into a size-0 and a size-(n−1) piece — giving a recurrence of T(n) = T(n−1) + O(n), which sums to O(n²), no better than insertion sort. This is a real, well-known adversarial case, not a theoretical curiosity: some early production incidents were traced to exactly this — a "sort" call quietly going quadratic on data that happened to already be sorted.

The standard, sufficient fix is a randomly chosen pivot (or the median-of-three heuristic — sample the first, middle, and last elements and use their median): this makes the O(n²) case astronomically unlikely for any fixed input, because the adversary would need to know your random seed in advance to construct a bad case. It does not eliminate the worst case in theory — say "expected O(n log n) with randomization," never "worst-case O(n log n)," unless you're using a more involved deterministic pivot-selection scheme (median-of-medians), which is essentially never expected to be implemented from scratch in an interview.

Dutch National Flag: three-way partitioning for duplicate-heavy arrays

Standard two-way partitioning degrades badly when the array has many duplicate values equal to the pivot — Lomuto/Hoare partitioning still does O(n) comparisons per pivot value, and if most elements are equal, you get a lopsided, close-to-worst-case split repeatedly. Edsger Dijkstra's Dutch National Flag problem (named for the three horizontal bands of the Dutch flag: red, white, blue) solves the specific case of partitioning into exactly three groups — less than, equal to, and greater than a pivot — in a single O(n) pass with O(1) space, using three pointers:

def dutch_flag_partition(arr, pivot):
    low, mid, high = 0, 0, len(arr) - 1
    while mid <= high:
        if arr[mid] < pivot:
            arr[low], arr[mid] = arr[mid], arr[low]
            low += 1
            mid += 1
        elif arr[mid] == pivot:
            mid += 1
        else:
            arr[mid], arr[high] = arr[high], arr[mid]
            high -= 1
            # do NOT advance mid here — the swapped-in element from the
            # high end hasn't been classified yet

Plugging this in as quicksort's partition step (3-way quicksort) gives you an algorithm whose performance actually improves as duplicates increase, instead of degrading — the "equal" band is fully resolved and never recursed into again, so an array of all-equal elements sorts in O(n), not O(n²). This is the single most important practical robustness fix on top of vanilla quicksort, and it's exactly the kind of follow-up ("what if the array has a lot of duplicate values?") that separates a candidate who memorized quicksort from one who understands its failure modes.

Quicksort vs. quickselect — reusing the same partition for two different questions

You've already seen quickselect in the Heaps topic: it's quicksort's partition step, but instead of recursing into both sides, it recurses only into the side containing the target rank and discards the other entirely — which is what takes the expected cost from O(n log n) down to expected O(n). The relationship is worth stating precisely:

	Quicksort	Quickselect
Question answered	"Put everything in order"	"What's the kth smallest/largest element?"
Recursion	Both partitions	Only the partition containing the target rank
Expected time	O(n log n)	O(n)
Worst case	O(n²) (bad pivots every time)	O(n²) (same cause)
Space	O(log n) (recursion stack, expected)	O(1) extra

If an interview question only ever asks for a single order statistic (median, kth largest, kth percentile) rather than a fully sorted output, quickselect is strictly the better tool — sorting the whole array to answer one rank query is doing O(n log n) of work to extract O(1) bits of information you actually need.

Complexity summary

	Time (expected)	Time (worst)	Space
Quicksort (randomized pivot)	O(n log n)	O(n²)	O(log n) expected (recursion stack)
Quicksort (3-way, many duplicates)	O(n) to O(n log n) depending on duplicate density	O(n²) (still possible on adversarial distinct values)	O(log n) expected
Quickselect	O(n)	O(n²)	O(1) extra

Pitfalls and interview gotchas

Deterministic pivot choice on data you don't control. Always randomize (or use median-of-three) unless you have a specific reason not to — "always pick the last element" is a textbook simplification, not a production-safe default.
Off-by-one at partition boundaries. quicksort(arr, lo, p - 1) / quicksort(arr, p + 1, hi) — recursing on [lo, p] or [p, hi] (including the pivot's own final position in a recursive call) causes infinite recursion on some inputs. Trace a 2-3 element example by hand before trusting the boundary math.
Forgetting to advance mid in the Dutch flag "equal" branch, or advancing it in the "greater" branch. The "greater" swap brings an unclassified element into arr[mid]'s position — it must be re-examined, not skipped.
Overclaiming worst-case complexity. Say "expected O(n log n)" for randomized quicksort and "expected O(n)" for quickselect — precision here is exactly what a rigorous interviewer is listening for.
Reaching for full quicksort when quickselect answers the actual question. If the problem only wants a single rank/order statistic, sorting everything is doing strictly more work than required — a good "can we do better?" answer in itself.

How to talk about this in an interview

"I'll partition around a randomly chosen pivot so everything smaller ends up on the left and everything larger on the right, then recurse on both sides — expected O(n log n), though an adversarial input with a bad pivot choice could hit O(n²), which randomization makes vanishingly unlikely rather than impossible. If there are a lot of duplicate values, I'd use a three-way Dutch-flag partition instead, so the equal band is resolved once and never recursed into again."

Further Resources (Optional)

Practice Problems

Interview relevancy:!!!Critical — must-have!!Important — highly recommended!Good to have~Niche — rarely asked

Sort Array By ParityEasy!1/515m
Partition Array According to Given PivotMedium!!3/525m
Wiggle Sort IIMedium!4/535m

Optional Practice (Extra Reps)

For once you've cleared the main set above and want more reps on this pattern. These don't count toward the roadmap's progress stats — solve them purely for your own benefit.

Quicksort 1 - PartitionHackerRank~2/520m