What you'll learn
Sorting is the most-studied problem in computing, and the three elementary sorts are where everyone starts. They're all O(n²), but comparing them teaches the vocabulary — comparisons, swaps, stability, in-place — you'll use to judge every algorithm after.
By the end you'll be able to:
- Trace bubble, selection, and insertion sort
- Explain what makes a sort stable and in-place
- Know which elementary sort to prefer, and when
Bubble sort
Repeatedly walk the list, swapping any out-of-order neighbors. After each pass the largest remaining value "bubbles" to the end. Simple, but it does the most work of the three:
Selection sort
Find the smallest element and swap it to the front; repeat for the rest. It makes at most n swaps — the fewest of any comparison sort — but still O(n²) comparisons:
Insertion sort
Grow a sorted region on the left, inserting each next value where it belongs — exactly how most people sort a hand of cards. It's the best elementary sort in practice: O(n) on nearly-sorted data and great for small arrays.
def insertion_sort(a):
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key: # shift bigger items right
a[j + 1] = a[j]
j -= 1
a[j + 1] = key # drop key into place
return aStability & in-place
Two properties we'll ask of every sort:
- Stable: equal elements keep their original relative order. This matters when sorting records by one field after another. Bubble and insertion are stable; selection is not.
- In-place: uses only
O(1)extra memory. All three elementary sorts are in-place.
Note
O(n log n) sorts because its constant factor is so low — which is why real library sorts fall back to it for small pieces.Complexity
| Sort | Best | Worst | Stable? | Swaps |
|---|---|---|---|---|
Bubble | O(n) | O(n²) | Yes | O(n²) |
Selection | O(n²) | O(n²) | No | O(n) |
Insertion | O(n) | O(n²) | Yes | O(n²) |
Recap & quick check
Key takeaways
- Bubble, selection, and insertion sort are all O(n²) worst case and in-place.
- Bubble and insertion are stable; selection is not.
- Selection makes the fewest swaps (O(n)); insertion shines on nearly-sorted data.
- Stable = equal items keep their order; in-place = O(1) extra memory.
- Insertion sort is the go-to for small or almost-sorted arrays.
Quick check
1. Which elementary sort is best on nearly-sorted data?
2. What does it mean for a sort to be stable?
3. Which sort makes the fewest swaps?
4. What is the worst-case time of all three elementary sorts?
To go faster than O(n²) we need a better idea: divide and conquer. Next up: Module 8 — Merge Sort & Quick Sort.