How do merge sort and quicksort work?

Q: How do merge sort and quicksort work?

# How Merge Sort and Quicksort Work (Python) **Target Audience:** Beginners preparing for coding interviews; basic loops, arrays and functions are enough. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact word an interviewer expects. All code is Python, and every output block was produced by actually running the programs (Python 3.13.16); nothing is quoted from memory. ## 1. Why This Even Matters — A Story First You have a messy stack of 1,000 exam papers to put in roll-number order, and two friends offer to help. The first friend says: "Cut the stack in half, give one half to someone else, sort your half, and when both halves are sorted I will **merge** them — I just keep taking whichever top paper has the smaller number." Each helper does the same thing with their half, until someone is holding a single paper, which is trivially sorted. That

The problem

Question presented to candidate: "Explain how merge sort and quicksort work — walk me through each on a small array — and then implement one of them in Python. What are their time and space costs, and when does quicksort go wrong?"

What a strong answer should cover:

Both are divide and conquer; merge sort does its work in the merge, quicksort in the partition.
Merge sort: split at the middle, recurse, two-pointer merge; O(n log n) in every case, O(n) extra space, stable because ties come from the left.
Quicksort: pivot, partition (Lomuto or Hoare), recurse on both sides; O(n log n) average, O(n²) worst case, O(log n) average stack, not stable.
Explains the worst case (sorted input with a first/last pivot) and the fixes: random or median-of-three pivot, introsort, recursing on the smaller side.
Python specifics: slices copy (O(n) extra memory), // for the midpoint, CPython's 1000-frame recursion limit, and that sorted (Timsort) is the production answer.

Clarifying questions expected:

Should the sort be in place, or may I use extra memory?
Does it need to be stable?

Code / implementation expected: Yes — a working Python merge sort or quicksort, with the base case and the merge or partition step correct.

dsa
sorting
divide-and-conquer
recursion

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

How Merge Sort and Quicksort Work (Python)

Target Audience: Beginners preparing for coding interviews; basic loops, arrays and functions are enough. Difficulty: Medium Language: Python 3

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact word an interviewer expects. All code is Python, and every output block was produced by actually running the programs (Python 3.13.16); nothing is quoted from memory.

1. Why This Even Matters — A Story First

You have a messy stack of 1,000 exam papers to put in roll-number order, and two friends offer to help.

The first friend says: "Cut the stack in half, give one half to someone else, sort your half, and when both halves are sorted I will merge them — I just keep taking whichever top paper has the smaller number." Each helper does the s

The solution is hidden so you can try first

11 min read · 12 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonMerge sort with a trace of every merge

Practice

PythonQuicksort trace, and last vs middle pivot on sorted input

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.