Micro-questions over the quicksort module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.


A. Why it exists

1. Compare quicksort with merge sort on memory.

Answer

Merge sort needs extra; quicksort needs only of stack.

2. Why is quicksort faster in practice despite a similar comparison count?

Answer

The reason is memory, not operation count. Partitioning sweeps sequentially and swaps in place — friendly to caches and prefetchers. Merge sort copies into and out of a separate buffer, doubling memory traffic. Constants win.

3. What is the price?

Answer

A genuine worst case. Merge sort’s split is by position and cannot be unbalanced; quicksort’s split is by value, so an unlucky input makes every partition lopsided — .


B. Partitioning

4. What does partitioning do?

Answer

Choose a pivot; rearrange so everything smaller is left of it and everything larger is right. The pivot is now in its final position. Recurse on both sides.

5. Describe Lomuto partitioning.

Answer

Pivot is the last element. Walk with j, keeping i as the boundary of the “smaller” region; swap into place whenever a[j] <= pivot. Finally swap the pivot to i+1.

6. Where does Lomuto degrade badly, and why?

Answer

On arrays of equal elements — every element satisfies <= pivot, so every partition is maximally lopsided and the sort goes quadratic on input that is already trivially sorted.

7. Describe Hoare partitioning and its advantages.

Answer

Two pointers move towards each other, swapping out-of-place pairs. It does about three times fewer swaps on average and handles duplicates far better, because elements equal to the pivot can end up on either side, which keeps partitions balanced.

8. Why is Lomuto taught first?

Answer

Only because Hoare’s index handling is fiddlier.


C. The worst case

9. What quantity actually decides the complexity?

Answer

The recursion depth. Balanced splits give depth and ; maximally lopsided splits give depth and .

10. With a last-element pivot, what is the worst case?

Answer

Already-sorted input — the pivot is always the maximum, so one side gets everything.

11. Why is that damning rather than a curiosity?

Answer

It is not a rare adversarial input; it is the most common input shape there is.

12. Give the five fixes and what each does.

Answer
FixWhat it does
Median-of-threepivot on median of first/middle/last — kills sorted input cheaply
Randomised pivotno fixed input is worst-case; an adversary cannot predict it
Introsortpast depth , switch to heapsort — a hard ceiling
Three-way partitionsplit into < = >; makes duplicate-heavy arrays linear
Insertion sort below ~16better constants on small partitions

13. What is std::sort?

Answer

Introsort with all five. That is why the standard library never exhibits the worst case even though the underlying algorithm has one.

14. Rank these three for a last-element pivot: random, reverse-sorted, all-identical.

Answer

Random is fine (). Reverse-sorted is — the pivot is always the minimum. All-identical is also under Lomuto and is the case people forget, because the array is already “sorted”.


D. Stability

15. Why is quicksort not stable?

Answer

Partitioning swaps elements across long distances. Two equal elements can be exchanged or jumped past one another, and their original order is lost.

16. Why do libraries not just fix it?

Answer

Making it stable requires extra space, which surrenders quicksort’s main advantage.

17. What do libraries offer instead?

Answer

A choice: sort (quicksort-family, unstable, fast) and stable_sort (merge-family, stable, memory). Python’s list.sort is Timsort and always stable — a deliberate different trade.


E. Traps

18. What is the Hoare off-by-one?

Answer

Hoare returns j and you recurse on [lo, j] and [j+1, hi] — not [lo, j-1]. Getting it wrong causes infinite recursion.

19. How do you cap the stack depth at ?

Answer

Recurse into the smaller side and loop on the larger. The recursed side at most halves each time.

20. Does randomisation make the worst case impossible?

Answer

No — it makes it improbable and input-independent. It is still reachable, just not by an adversary choosing the input.

21. Summarise quicksort in one sentence.

Answer

Partition in place around a pivot and recurse — the fastest in practice because it stays in cache, and safe only because libraries median-of-three it, randomise it, and cap its depth with heapsort.


Scorecard

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Sorting