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.
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 numsHalve 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.
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 resultAt 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.
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 aloneEqual 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) | ✕ | ✓ | ✕ |
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. |