A teacher has 60 answer sheets and wants them in roll-number order. Watch what she actually does: picks up the next sheet, slides it into its correct place among the already-sorted pile in her hand. Sheet by sheet, done in minutes. Nobody taught her an algorithm — yet she just executed one, correctly, that computer science has a name for.
Sorting is the perfect first algorithms topic because the whole subject appears here in miniature: one job, six honest ways to do it, with costs ranging from "instant" to "come back after lunch" — and a trade-off attached to every choice. Learn to compare sorts and you have learned to compare algorithms.
What would we naturally invent?
Before any names, invent sorting yourself. Given [5, 1, 4, 2, 8], what would you do?
Most people invent one of two ideas. Idea one: find the smallest, put it first; find the next smallest, put it second... — that's selection sort. Idea two: walk the array swapping any neighbours that are out of order, repeatedly — that's bubble sort. Watch one full bubble pass:
Notice what one pass achieves: the largest element (8 was already there; in general, the largest) has "bubbled" to the end — but the rest is still messy. One pass places ONE element, so we need up to n−1 passes.
The teacher's method: insertion sort
The teacher's card trick is the third natural idea, and the best of the simple family: keep the left part of the array sorted; take the next element; shift bigger elements right; drop it into its gap.
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i] # the next answer sheet in hand
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j] # shift the bigger sheet right
j -= 1
arr[j + 1] = key # drop into the gap
return arr
print(insertion_sort([7, 3, 5, 1]))start: [7, 3, 5, 1] insert 3: 7 shifts -> [3, 7, 5, 1] insert 5: 7 shifts -> [3, 5, 7, 1] insert 1: 7,5,3 shift -> [1, 3, 5, 7]
And one hidden superpower, worth filing now: on a nearly sorted array, almost nothing shifts — the while loop exits immediately — and insertion sort runs in nearly O(n). Real libraries exploit exactly this; hold the thought for the last section.
Why are all three simple sorts O(n²)?
Bubble, selection, insertion — all O(n²). Coincidence? No, and seeing why is the doorway to the fast sorts. All three share one habit: they compare neighbouring or nearly-neighbouring elements, so each comparison moves an element at most one position toward its home. An element that starts n positions from home needs ~n comparisons of its own; n elements × n positions = n².
Now name the waste precisely: each comparison earns only one position of progress. To beat n², a comparison must somehow earn MORE — move elements long distances, or settle many relationships at once. Every fast sort is a scheme for making comparisons earn more.
The observation that breaks the wall: merge sort
Here is the key observation. Suppose someone hands you two piles of answer sheets, each already sorted. Combining them into one sorted pile is suddenly easy — only the two top sheets ever compete; take the smaller, repeat. Each comparison permanently places one sheet: maximum value per comparison.
But who gives us sorted piles? We make them ourselves — by splitting: half of a pile, sorted the same way, becomes a sorted pile. Split until piles have one sheet (trivially sorted), then merge back up. This split–solve–combine strategy is divide & conquer (lesson 5); merge sort is its poster child:
The cost picture, straight from the triangle: log n levels of halving, and each level's merges touch all n elements once — n work per level × log n levels = O(n log n), and no input can make it worse. At n = 1 lakh: ~17 lakh steps versus n²'s 1,000 crore. The price: merging needs a scratch buffer — O(n) extra memory.
Dry run: the merge step
The merge is where all the work lives, so let's trace it honestly. Merging left = [2, 7, 9] and right = [1, 8]:
def merge(left, right):
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= and not < : remember this!
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
out.extend(left[i:]) # one side ran dry:
out.extend(right[j:]) # append the leftovers
return outcompare 2 vs 1 -> take 1 out=[1] compare 2 vs 8 -> take 2 out=[1,2] compare 7 vs 8 -> take 7 out=[1,2,7] compare 9 vs 8 -> take 8 out=[1,2,7,8] right exhausted -> extend [9] -> [1,2,7,8,9] 4 comparisons placed 5 elements - every comparison earned
Why <= and not <? On ties, the LEFT element goes first — preserving the original order of equal elements. That tiny choice has a name and its own section below.
Quicksort: divide from the other end
Merge sort splits mechanically (at the midpoint) and works hard to combine. Quicksort flips the effort: work hard on the split, and combining becomes free. Pick an element — the pivot — and partition: rearrange so everything smaller sits to its left, everything bigger to its right. Now the pivot is in its final sorted position, and the two sides can be sorted independently — no merge needed, no scratch buffer, all in place.
def quicksort(arr, lo=0, hi=None):
if hi is None:
hi = len(arr) - 1
if lo < hi:
p = quicksort_partition(arr, lo, hi) # pivot's final home
quicksort(arr, lo, p - 1)
quicksort(arr, p + 1, hi)
def quicksort_partition(arr, lo, hi): # Lomuto: last element pivots
pivot = arr[hi]
i = lo - 1 # right edge of the "< pivot" zone
for j in range(lo, hi):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
return i + 1Now the question interviews live on: what if the pivot is terrible? A good pivot splits the array roughly in half — log n levels, O(n log n) overall, with small constants and lovely cache behaviour (usually the fastest comparison sort in practice). A terrible pivot — the smallest or largest element — splits n items into 0 and n−1: the recursion becomes a chain of depth n, each level scanning what remains. n + (n−1) + ... = O(n²).
And the trigger is embarrassingly ordinary: a sorted array with first/last-element pivots is quicksort's WORST case — every pivot is an extreme. People guess "best case" here constantly; now you know better, and you know the fixes: pick pivots randomly, or take the median of first/middle/last. Either makes the worst case practically unreachable.
🎯 Selection-round radar: "quicksort vs merge sort" is the most-reported sorting question at every company tier. The complete answer touches four axes: average/worst case, memory (in place vs O(n)), stability (next section), and one sentence on why quicksort still wins in practice (cache + constants).
Stability: the property everyone forgets
A sort is stable if equal elements keep their original relative order. Sounds academic — until the elements are real records:
orders = [("Asha", "Delhi"), ("Vikram", "Mumbai"),
("Meena", "Delhi"), ("Ravi", "Mumbai")]
# currently in DATE order; now sort by city
by_city = sorted(orders, key=lambda o: o[1])
print(by_city)Result
[('Asha', 'Delhi'), ('Meena', 'Delhi'), ('Vikram', 'Mumbai'), ('Ravi', 'Mumbai')]Within each city, the date order survived — because Python's sort is stable. That is what makes multi-stage sorting work: sort by date, then stably by city, and each city's orders stay chronological. Merge sort (with that <=) and insertion sort are stable; selection sort and plain quicksort are not. When an interviewer asks "why would you ever pick merge sort despite the memory cost?" — stability plus the guaranteed worst case IS the answer.
What if we never compare at all?
One more wall to break. Theory proves comparison-based sorting cannot beat O(n log n) — with n! possible orderings, each comparison splits the possibilities in two, so you need at least log₂(n!) ≈ n log n of them. Solid proof. So sorting 10 lakh exam marks must cost ~17 lakh × 20 steps... right?
Look for the loophole: the proof binds comparison sorts. Marks are integers 0–100 — a tiny known range. Don't compare; count:
def counting_sort(marks, k=100): # values 0..k
counts = [0] * (k + 1)
for m in marks: # pass 1: tally each value
counts[m] += 1
out = []
for value in range(k + 1): # pass 2: replay in order
out.extend([value] * counts[value])
return out
print(counting_sort([64, 22, 98, 22, 75, 64, 22]))Result
[22, 22, 22, 64, 64, 75, 98]
O(n + k) — for 10 lakh marks and k = 101, about 10 lakh steps, genuinely faster than any comparison sort. A small known range is a licence to count instead of compare. The catch: counting-sort 64-bit integers and the counts array outgrows the universe — k must be small. (Radix sort extends the idea digit by digit; know the name.)
What real libraries actually use
Python's sorted() runs Timsort: merge sort's skeleton, detecting already-sorted runs in real data and extending short runs with insertion sort — stable, O(n log n) worst case, nearly O(n) on the partially-sorted data real systems produce. C++'s std::sort runs introsort: quicksort that switches to heap sort if recursion gets suspiciously deep, beheading the O(n²) worst case.
Notice: the libraries are the textbook sorts, composed. So the practical rule is honest, not lazy: call the library sort — you won't beat it. Interviews ask you to hand-write sorts to test understanding, then expect you to say exactly this sentence.
What if...?
What if the array is already sorted? Insertion sort: O(n), its best case. Bubble with an early-exit flag: O(n). Naive quicksort: O(n²), its WORST case — the inversion that catches everyone. Merge sort: O(n log n) regardless, blind to luck.
What if all elements are equal? Every comparison ties. Stable sorts shrug; Lomuto-partition quicksort degrades to O(n²) (every element lands on one side) — the three-way partition variant exists for exactly this.
What if the array is tiny — say 10 elements? Insertion sort beats everything on constants; that's why Timsort and introsort both hand small runs to it.
What if I only need the 10 largest of a crore? Don't sort at all — a size-10 heap does it in O(n log 10). Sorting everything to read ten values is the over-sorting mistake from the heaps lesson.
Common mistakes
- Saying "quicksort is O(n log n)" without the average-vs-worst qualifier — the qualifier IS the question.
- Believing sorted input is quicksort's best case — with naive pivots it's the worst.
- Forgetting merge sort's O(n) extra memory in comparisons.
- Claiming one bubble pass sorts the array — it places one element.
- Reaching for quicksort on marks 0–100 — the small range begs for counting sort.
- Using an unstable sort in multi-stage sorting, then wondering where the earlier ordering went.
How sorting shows up in interviews
- Written MCQs: "array after one pass of X" — bubble places the max at the end; selection places the min at the front; insertion sorts the left prefix. Trace, don't recall.
- Comparison theory: quick vs merge (the four axes), stability scenarios, "name an in-place guaranteed O(n log n) sort" (heap sort).
- Recognition: small value range → counting sort; nearly sorted → insertion; top-K → heap, not sort.
- As a preprocessing step: half the techniques in this course (binary search, two pointers, greedy) begin with "first, sort" — the O(n log n) is often the whole price of admission.
Quick revision
| Sort | Average | Worst | Space | Stable? |
|---|---|---|---|---|
| Bubble | O(n²) | O(n²) | O(1) | yes |
| Selection | O(n²) | O(n²) | O(1) | no |
| Insertion | O(n²); ~O(n) nearly sorted | O(n²) | O(1) | yes |
| Merge | O(n log n) | O(n log n) | O(n) | yes |
| Quick | O(n log n) | O(n²) — bad pivots | O(log n) stack | no |
| Counting | O(n + k) | O(n + k) | O(k) | yes |
One thing to remember
Slow sorts earn one position per comparison; fast sorts make every comparison earn more — merging sorted halves, or partitioning around a pivot. Judge any sorting idea by what one comparison buys.
Practice Zone — PYQs from real selection rounds
Six MCQs, then three traces: insertion sort step by step, the merge step with comparisons counted, and one full Lomuto partition.
After ONE full pass of bubble sort on [5, 1, 4, 2, 8], the array is:
Asked in
Which sorting algorithm is O(n log n) in the WORST case, guaranteed?
Asked in
A STABLE sort is one that:
Asked in
Quicksort's worst case O(n²) happens when:
Asked in
Merge sort's main practical COST compared to quicksort is:
Asked in
Sorting 10 lakh exam marks, each an integer 0–100, the FASTEST approach is:
Asked in
Hands-on tasks:
Sort [7, 3, 5, 1] with insertion sort and write the array state after each element is inserted.
Asked in
Write the merge step of merge sort and trace it on left = [2, 7, 9], right = [1, 8]. Count the comparisons.
Asked in
Partition [8, 3, 7, 1, 9, 2] around the last element as pivot (Lomuto). Show the array after each swap and give the pivot's final index.
Asked in
FAQ
Which sorting algorithms should I be able to hand-write?
Insertion sort and the merge step, fluently; the partition for quicksort; and counting sort as an explanation. More valuable than code: the recap table above, cold — most sorting questions are comparisons, not implementations.
Where does heap sort fit?
Heapify the array (O(n)), then extract the max n times: O(n log n) worst case, in place, not stable. It's the answer to "in-place AND guaranteed n log n?" — the combination neither merge nor quick offers — and it reuses the heap machinery you already own.
Why is bubble sort taught at all if nobody uses it?
It's the minimal example of an algorithmic idea (local swaps → global order) and a standing written-test question ("array after one pass"). Its one honest variant — stop early if a pass made no swaps — is also a first taste of adaptive algorithms.
Is citing Timsort in an interview showing off?
It's a strong closing line — naming it, its stability, and its near-O(n) behaviour on real-world data. Just be ready for the follow-up ("so how does merge sort work inside it?"), which this lesson has you covered for.
Sorting done — and sorted data is a superpower waiting to be spent. Next, the algorithm that spends it best — Lesson 2: Binary Search →