Computer Science I / Divide-and-Conquer Reasoning
Practice question · Multiple choice

Merge sort guarantees O(n log n) and quicksort is usually preferred anyway. What is quicksort buying, and what is it risking?

Hints
  1. Ask how much extra memory each algorithm needs.
  2. What input makes quicksort with a naive pivot behave quadratically?
Show the answer

D. A smaller constant and in-place operation, at the risk of O(n²)

Why

Quicksort partitions in place with excellent cache behaviour, where merge sort allocates a second array, a real cost at scale. The price is a quadratic worst case on sorted input with a naive pivot, mitigated by randomised or median-of-three pivots and by falling back to heapsort, which is what introsort does.

Read the lesson: Divide-and-Conquer Reasoning →

Practise Divide-and-Conquer Reasoning

The app has 6 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.

More questions on Divide-and-Conquer Reasoning