Sorting
16 min
Sorting is one of the most-studied problems in computer science because
almost everything else — search, deduplication, grouping — gets easier once
data is ordered. In real code you'll almost always call sorted(), but
understanding how a simple sort works builds the intuition you need for
harder algorithms later.
Bubble sort repeatedly walks the list, swapping any adjacent pair that's out of order, until a full pass makes no swaps. It's O(n²) — never use it in real code — but it's the clearest place to see "comparison-based sorting" in action.
Each outer pass 'bubbles' the largest remaining element to its final position — after i passes, the last i elements are guaranteed sorted.
In practice, Python's sorted() (Timsort — O(n log n), and stable,
meaning equal elements keep their relative order) is what you'll use. The
key argument is how you sort by something other than the raw value:
words = ["banana", "kiwi", "fig"]
sorted(words, key=len) # ['fig', 'kiwi', 'banana']
sorted(words, key=lambda w: (len(w), w)) # sort by length, then alphabetically
sorted(words, reverse=True) # descending
Stability matters when you sort by a tuple key like (len(w), w) above —
you're relying on ties in the first key being broken deterministically by
the second.
Write a function `bubble_sort(nums)` that returns a NEW list containing the elements of `nums` sorted in ascending order, implemented with the bubble sort algorithm (repeatedly swap adjacent out-of-order pairs).
Write a function `sort_by_length_then_alpha(words)` that returns `words` sorted first by string length (ascending), then alphabetically to break ties. Use `sorted()` with a `key`.
What sorting algorithm does Python's built-in `sorted()` / `list.sort()` use, and what's its average time complexity?
You can implement a basic O(n²) sort by hand and use sorted(..., key=...) for real sorting work.