Quick Sort and Partitioning

Quicksort is the fastest general-purpose in-place sort in practice, averaging O(n log n) with excellent cache behaviour, and its partitioning routine is the engine behind Quickselect (kth element) and Dutch-flag problems. The catch interviewers probe: a bad pivot gives O(n²).

The core idea

Pick a pivot, partition the array so smaller elements go left and larger go right (the pivot lands in its final position), then recursively sort each side. Average O(n log n); worst O(n²) when pivots are consistently extreme (e.g., already-sorted input with a first/last pivot). Randomised or median-of-three pivots make the worst case improbable. It's in-place (O(log n) recursion stack) but not stable. Partition schemes: Lomuto (simpler) and Hoare (fewer swaps).

Aspect	Value
Average time	O(n log n)
Worst time	O(n²)
Space	O(log n) stack
Stable	No
Pivot fix	random / median-of-three

Exam Tricks & Tips

• 🎯 Average O(n log n), worst O(n²) — state both; the worst case comes from bad pivots.
• 🎯 Randomised or median-of-three pivot avoids the sorted-input O(n²) trap.
• 🎯 Partitioning is the reusable part: Quickselect finds the kth element in O(n) average.
• 🎯 Quicksort is in-place and cache-friendly — usually faster than merge sort in memory.
• 🎯 Recurse into the smaller partition first to bound stack depth at O(log n).
• ❌ Common mistake: always choosing the first/last element as pivot, giving O(n²) on sorted data.

Expected pattern

Implement quicksort/partition, Quickselect for kth largest, sort colors (Dutch flag), or "why can quicksort be O(n²)?". Interviewers grade the partition logic, pivot strategy, and complexity nuance.

Quick recap

Quicksort partitions around a pivot and recurses — average O(n log n), worst O(n²) on bad pivots (fix with randomisation/median-of-three). In-place, O(log n) stack, not stable. Its partition powers Quickselect (O(n) average kth element).

Cover the answer, recall, then check. 11 cards on quicksort and partitioning.

Q1. Quicksort's average and worst-case time?
A1. O(n log n) average, O(n²) worst case.

Q2. What triggers the O(n²) worst case?
A2. Consistently extreme pivots (e.g., first/last pivot on already-sorted input).

Q3. How do you avoid the worst case?
A3. Randomised pivots or median-of-three pivot selection.

Q4. Is quicksort stable?
A4. No — partitioning can reorder equal elements.

Q5. Quicksort's space complexity?
A5. O(log n) recursion stack (in-place partitioning), O(n) stack in the worst case.

Q6. What does the partition step accomplish?
A6. Places the pivot in its final sorted position with smaller elements left and larger right.

Q7. Quickselect complexity for the kth element?
A7. O(n) average, O(n²) worst — recurse into only one partition.

Q8. Lomuto vs Hoare partition — difference?
A8. Lomuto is simpler (pivot at end); Hoare uses two pointers and does fewer swaps on average.

Q9. Why is quicksort often faster than merge sort in memory?
A9. In-place operation and good cache locality give it smaller constant factors.

Q10. How do you bound recursion depth at O(log n)?
A10. Recurse into the smaller partition first (tail-call the larger).

Q11. Sort Colors (0/1/2) relation to quicksort?
A11. It's a single three-way (Dutch National Flag) partition — O(n)/O(1).

Quicksort is the fastest general-purpose sort in practice, the default in most standard libraries, and its partition step is a reusable powerhouse (quickselect, Dutch flag). Its catch — an O(n²) worst case — is exactly what interviewers probe.

Core idea: pick a pivot, partition the array so smaller elements go left and larger go right (the pivot lands in its final sorted position), then recursively sort the two sides. Partitioning is O(n), and good pivots give log n depth → O(n log n) average.

How it works

Beginner — partition and recurse

def quickSort(a, lo, hi):
    if lo < hi:
        p = partition(a, lo, hi)   # pivot now in final place
        quickSort(a, lo, p-1)
        quickSort(a, p+1, hi)

Lomuto partition: keep a boundary i; scan, swapping elements ≤ pivot to the left region; finally place the pivot at i. One O(n) pass.

Intermediate — the complexity split

• Average / best: balanced partitions → depth O(log n), work O(n) per level → O(n log n).
• Worst: always the smallest/largest pivot (e.g. already-sorted array with a naive last-element pivot) → depth O(n) → O(n²).
• Space: O(log n) average recursion (O(n) worst); in-place, no merge buffer.

Advanced — taming the worst case

• Randomised pivot or median-of-three makes the O(n²) case astronomically unlikely — the standard fix.
• Introsort (used by C++ std::sort) starts with quicksort and switches to heapsort when recursion gets too deep, guaranteeing O(n log n) worst case.
• Three-way (Dutch flag) partition handles many duplicate keys in O(n) at that level, avoiding quadratic blowup on repeated values.
• Quicksort is not stable; use merge sort when stability is required.

Worked example

Partition [7, 2, 1, 6, 8, 5, 3, 4] with pivot 4 (last). Scan, moving elements < 4 to the left: 2,1,3 go left of the boundary; result places 4 so that [2,1,3] | 4 | [6,8,5,7]. Pivot 4 is now in its final sorted index; recurse on each side. Each partition is O(n); balanced splits give O(n log n).

When to use it

• General-purpose in-place sorting where average speed and cache-friendliness matter (the library default).
• Quickselect: partition-based Kth smallest/largest in O(n) average without full sorting.
• When O(n) extra space (merge sort) is unacceptable and stability is not required.

Tricks & gotchas

• Always randomise or use median-of-three — a fixed pivot on sorted input is the classic O(n²) trap.
• Use three-way partitioning when the array has many duplicates.
• Quicksort is unstable; state this if the problem sorts by a secondary key.
• Mnemonic: "Partition puts the pivot home; random pivots dodge the quadratic trap."

Key formulas

• Average Θ(n log n); worst Θ(n²) (already-sorted with a bad pivot).
• Best-case recurrence T(n)=2T(n/2)+Θ(n) ⇒ Θ(n log n).
• In-place, O(log n) recursion space; not stable.
• Partition step Θ(n); randomised pivot ⇒ expected Θ(n log n).
• Expected comparisons ≈ 1.39 n log₂ n.
• Quickselect (k-th element): average Θ(n).

Usage: randomise or use median-of-three pivots to avoid the O(n²) worst case.

Worked Example

Problem: Apply one Lomuto partition to [7, 2, 1, 6, 8, 5, 3, 4] using the last element (4) as pivot. Where does the pivot end up?

Solution: Lomuto keeps a boundary index i (last position holding a value ≤ pivot). Scan j across the array; whenever a[j] ≤ pivot, advance i and swap a[i], a[j].

• j=0: 7 > 4 → skip.
• j=1: 2 ≤ 4 → i=0, swap → [2, 7, 1, 6, 8, 5, 3, 4]
• j=2: 1 ≤ 4 → i=1, swap → [2, 1, 7, 6, 8, 5, 3, 4]
• j=3..5: 6, 8, 5 all > 4 → skip.
• j=6: 3 ≤ 4 → i=2, swap → [2, 1, 3, 6, 8, 5, 7, 4]

Finally swap the pivot into position i+1 = 3: [2, 1, 3, 4, 8, 5, 7, 6].

The pivot 4 rests at index 3, with all smaller values to its left and larger to its right.

Quicksort averages O(n log n) but degrades to O(n²) on bad pivots.

Answer: After partition the pivot 4 lands at index 3.