Compare common sorting algorithms.

Q: Compare common sorting algorithms.

# Comparing Common Sorting Algorithms (Python) **Target Audience:** Beginners preparing for coding interviews; you only need to know what an array and a loop are. **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 Picture a teacher handing back 200 exam papers that must be put in order of roll number. One helper picks up each paper and slides it into the right place in the pile already in their hand. Another helper splits the stack in half, gives each half to a friend, and later merges the two sorted halves by repeatedly taking the smaller top paper. A third picks a "middle" roll number, throws everything smaller to the left and everything

The problem

Question presented to candidate: "Walk me through the common sorting algorithms — bubble, selection, insertion, merge, quick and heap sort. How do they compare, and which would you pick in different situations? Feel free to show code in Python."

What a strong answer should cover:

Compares on the right axes: best, average and worst time, extra space, stability and adaptivity.
Correct complexities: the three simple sorts are O(n²); merge and heap sort are O(n log n) always; quicksort is O(n log n) average but O(n²) worst case.
Explains why quicksort is still popular (in place, cache-friendly, good pivots make the worst case unlikely) and what introsort or random pivots do.
Mentions the n log n lower bound for comparison sorts and when counting or radix sort can beat it.
Knows that Python's sorted/list.sort is a stable Timsort-family sort, that sort() returns None, and that key= is preferred over a comparator.
Picks an algorithm from the input shape: nearly sorted, needs stability, tight memory, linked list, small integer keys.

Clarifying questions expected:

How big is the input, and is it nearly sorted already?
Do equal keys need to keep their original order (stability)?
Is extra memory a constraint, and is the data an array or a linked list?

Code / implementation expected: Optional — a short Python implementation of one O(n²) and one O(n log n) sort is a good bonus; the comparison and the choice matter more.

sorting

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

Comparing Common Sorting Algorithms (Python)

Target Audience: Beginners preparing for coding interviews; you only need to know what an array and a loop are. 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

Picture a teacher handing back 200 exam papers that must be put in order of roll number. One helper picks up each paper and slides it into the right place in the pile already in their hand. Another helper splits the stack in half, gives each half to a friend, and later merges the two sorted halves by repeatedly taking the smaller t

The solution is hidden so you can try first

10 min read · 14 sections

Python code

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

PythonComparison counts: the three simple sorts

Practice

PythonComparison counts: merge, quick and heap sort

Practice

PythonStability: which sorts keep equal keys in order

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.