Elementary sorts

Bubble, selection, insertion — all O(n²). Insertion is the one that matters.

Three ideas

• Bubble — swap adjacent pairs; largest bubbles to the end
• Selection — find the min each pass; only n swaps
• Insertion — grow a sorted prefix, slide each element back
• All in-place, O(1) extra space

Watch insertion sort

Blue prefix grows; orange element slides into place. Nearly-sorted data → barely any movement.

O(n²) vs O(n log n)

At n=2000, insertion is 500× slower than Timsort — and the gap only grows.

Insertion sort is adaptive

• 8000 random elements: ~710 ms
• 8000 nearly sorted: ~38 ms → 19× faster
• Why Timsort uses it on small runs

Takeaway

Insertion sort for small / nearly-sorted; O(n log n) for the rest. Learn to read a nested loop as a quadratic. Next: merge sort.