Module 1 · The simple sorts
Compare, swap, repeat — the O(n²) sorts
📚 Tidying by hand: the three simplest sorts each tidy the shelf a different way — bubble swaps neighbours, selection hunts for the smallest, insertion slides each book back into a growing tidy pile. All three are easy to follow and all three are slow on big shelves.
Bubble sort — compare each neighbouring pair and let the biggest value bubble to the end each pass.
Whole numbers 1–99, up to 12 of them.
Start: compare each neighbouring pair and let the largest value bubble to the right.
Show the Python
def bubble_sort(nums):
n = len(nums)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
swapped = True
if not swapped: # a clean pass — already sorted
break
return numsModule 2 · Divide and conquer
Split the shelf — the O(n log n) sorts
✂️ Split the pile: instead of one long shelf, cut it in half again and again until every piece is trivially sorted, then merge the pieces back in order. Doing less comparing overall is what makes merge and quick sort so much faster on big inputs.
Halve the list again and again until every piece is length 1 (already sorted). Then merge pairs back together in order. The merging does the real work — and it costs O(n log n) whether the input is sorted, reversed, or random.
Whole numbers 1–99, up to 12 of them.
Split [5, 3, 8, 1] down the middle into [5, 3] and [8, 1].
Sorted result: [1, 3, 5, 8]
Show the Python
def merge_sort(nums):
if len(nums) <= 1:
return nums
mid = len(nums) // 2
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= keeps it stable
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
result.extend(left[i:])
result.extend(right[j:])
return resultModule 3 · How fast do they grow?
O(n²) vs O(n log n), side by side
📈 Big-O is the shape of the curve. On a tiny shelf every sort feels instant. The difference only shows up as the shelf grows — drag n and watch the slow sorts pull away.
At n = 10, an O(n²) sort does about 100 operations while an O(n log n) sort does about 33. Push n higher and the gap becomes a chasm.
Module 4 · Sorting by a key
Sort by anything, not just size
🔑 You choose the rule. Real sorting is rarely "smallest number first". Python's sorted(key=...) lets you sort by length, by last letter, by grade, or by several keys at once — same data, different rule.
sorted(words, key=len)Sorts by word length, shortest first. banana stays before cherry — both are 6 letters, so the original order is kept (stable).
In real code, you don't write the sort yourself
# Python's built-in sort is Timsort — O(n log n), stable
nums.sort() # sorts the list in place, returns None
ordered = sorted(nums) # returns a NEW sorted list, leaves nums aloneModule 5 · The vocabulary
Stable, in-place, adaptive — and the full comparison
🏷️ Three words describe every sort. Does it keep equal items in order (stable)? Does it avoid making a second copy (in-place)? Does it speed up on nearly-tidy shelves (adaptive)? Tap any row for the plain-English why.
Equal values keep their original relative order.
Lets you sort by one thing after another — sort by name, then by grade, and names stay in order inside each grade.
Sorts by rearranging the original list, using only O(1) extra memory.
Matters on huge lists or small devices where making a second full copy of the data won't fit.
Runs faster when the input is already partly sorted.
Real data is often nearly ordered. Insertion sort (and Timsort) finish in close to O(n) on it.
| Algorithm | Best | Average | Worst | Space | Stable | In-place | Adaptive | |
|---|---|---|---|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | O(1) | ✓ | ✓ | ✓ | |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | ✕ | ✓ | ✕ | |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | ✓ | ✓ | ✓ | |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | ✓ | ✕ | ✕ | |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n) | ✕ | ✓ | ✕ |
Module 6 · Why bother learning these?
Python already has sorted() — so why?
They teach the core pattern
Compare, swap, repeat. Every sort — even the clever ones — is built on the loop-and-compare idea you first meet here.
They win on tiny inputs
For ~10 items or fewer, their simplicity beats the overhead of recursion. Timsort itself drops to insertion sort on short runs.
Insertion sort is adaptive
On nearly-sorted data it runs in close to O(n) — sometimes faster than an O(n log n) sort with more overhead.
They're easy to prove correct
No recursion, no tricky merge edge cases. You can trace the whole thing by hand and be sure it works.
They build Big-O intuition
You can literally watch the nested loops run n × n times. Nothing makes O(n²) concrete like seeing it.
Interviews still ask
Coding and reasoning about the simple sorts — and knowing when each is the right pick — is a common interview warm-up.
Which sort should I reach for?
| When… | Use |
|---|---|
| Small list (≤ ~10) or nearly sorted already | Insertion sort — simple and adaptive. |
| You need a guaranteed O(n log n), even worst case | Merge sort — steady on any input. |
| You want speed on average and memory is tight | Quick sort — fast in practice, sorts in place. |
| Stability matters (sorting by more than one key) | Merge sort or Python's Timsort — both stable. |
| You just need it sorted, correctly, right now | Built-in sorted() / .sort() — Timsort, stable, O(n log n). |
| Teaching or debugging the idea by hand | Bubble or selection sort — easiest to trace. |
Where this connects
🔗 Looking forward: merge and quick sort are recursion with a base case — the same nesting-dolls idea. And "which sort?" is always a Big-O decision, the same trade-off you make every time you choose a data structure.