Elementary Sorts & the Play Chart
Tunebox's Play Chart ranks every track by how often it's been played. In
production that's one call to sorted() — but which order you get for ties,
how long it takes on 50,000 tracks, and why an almost-sorted chart re-sorts
instantly all come from how sorting works. Three simple sorts show all of it.
Bubble sort — swap neighbours until nothing moves
Walk the list comparing each pair of neighbours; swap any pair that's out of order. Each pass carries the largest remaining value to the end, like a bubble rising.
nums = [5, 1, 4, 2]
for j in range(len(nums) - 1):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
print(nums)Selection sort — pick the smallest, put it next
Find the smallest value in the unsorted part and swap it to the front of that part. Repeat with one fewer value each time.
Selection sort never gets lucky: it scans the whole unsorted part every time, so it makes n(n−1)/2 comparisons even on a list that was already sorted.
Insertion sort — grow a sorted prefix
Keep the left part sorted. Take the next value (the key), shift every bigger
value in the sorted part one place right, and drop the key into the gap. It's
how most people sort a hand of cards.
Watch j walk left while it finds bigger values, and notice where the key
lands: one place right of where j stopped. Getting that index wrong is the
usual insertion-sort bug:
This should print [10, 20, 30]. It prints [30, 30, 10] — the key is written over the wrong slot, and at j == -1 it even lands at the END of the list.
Why they're all O(n²)
Each sort has a loop inside a loop over the same data. Double the tracks and the work roughly quadruples:
4,950 → 19,900 → 79,800. At 50,000 tracks that's over a billion comparisons — which is why the next two lessons exist.
❓ Cross-question — "If they're all O(n²), why learn three?" Because they differ exactly where it matters in practice: whether ties survive, and how they behave on data that's almost sorted. That's the rest of this lesson.
Stability — what happens to ties
A sort is stable if items that compare equal keep their original relative order. The chart sorts by plays; two tracks with 12 plays are "equal", and a stable sort leaves them in library order.
tracks = [("Echo", 12), ("Aria", 40), ("Dawn", 12)]
ranked = sorted(tracks, key=lambda t: t[1])
print([title for title, plays in ranked])Bubble and insertion sort are stable: they only ever move a value past a strictly bigger neighbour. Selection sort is not — its long-distance swap can jump one tie over another:
Why it matters: stability lets you sort by several keys in passes. Sort by title first, then by plays — ties on plays stay in title order.
❓ Cross-question — "Can I make selection sort stable?" Yes — instead of swapping, remove the smallest and insert it at position
i, shifting the rest right. That shift is really insertion sort's move, and it costs more writes.
Insertion sort on nearly-sorted data
Insertion sort does work only for values that are out of place. On a sorted list
the while stops immediately every time — O(n). A chart where two tracks just
swapped places is nearly sorted, and insertion sort fixes it in a single pass.
def shifts(nums):
items, moved = list(nums), 0
for i in range(1, len(items)):
key, j = items[i], i - 1
while j >= 0 and items[j] > key:
items[j + 1] = items[j]
j -= 1
moved += 1
items[j + 1] = key
return moved
print(shifts([1, 2, 3, 4, 5]), shifts([5, 4, 3, 2, 1]))| sort | best | average | worst | extra space | stable |
|---|---|---|---|---|---|
| bubble (with early exit) | O(n) | O(n²) | O(n²) | O(1) | yes |
| selection | O(n²) | O(n²) | O(n²) | O(1) | no |
| insertion | O(n) | O(n²) | O(n²) | O(1) | yes |
sorted() / list.sort() |
O(n) | O(n log n) | O(n log n) | O(n) | yes |
Idioms & real-world patterns
In production: key= and reverse=
You'll almost never hand-write these sorts. You will need to say what order you
want — and Python's sort keeps ties stable even with reverse=True:
list.sort() sorts in place and returns None — chart = chart.sort() throws
the chart away. sorted() returns a new list.
Coming from Java/JS: Java's
Collections.sortandArrays.sorton objects are stable (TimSort);Arrays.sorton primitives isn't, but equal ints can't be told apart anyway. JS'ssorthas been stable since ES2019 — but with no comparator it compares as strings:[10, 9, 1].sort()is[1, 10, 9].
Insertion sort lives inside Timsort
Python's own sort, Timsort, finds runs that are already in order and uses insertion sort to extend short runs before merging them. It's O(n) on sorted input for the same reason insertion sort is.
⚡ Advanced — counting sort, when keys are small integers
Comparison sorts can't beat O(n log n). But star ratings are only 1–5, so you can skip comparing: count how many of each, then write them out. O(n + k) for k possible values:
🎯 Your turn
Write rank_tracks(tracks). Each track is {"title": ..., "plays": ...}. Return
the titles ordered by plays, most-played first; tracks with equal plays keep
the order they had in tracks. Sort them yourself — insertion sort fits — rather
than calling sorted() or .sort():
rank_tracks([{"title": "Dawn", "plays": 12}, {"title": "Aria", "plays": 40}, {"title": "Blue", "plays": 25}])→["Aria", "Blue", "Dawn"]rank_tracks([{"title": "Echo", "plays": 12}, {"title": "Dawn", "plays": 12}])→["Echo", "Dawn"]
Hint — insertion sort, but shift a track right only while the one to its left has fewer plays than the key — strictly fewer, so ties never swap.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of Tunebox is built. ✅