The Core Idea
Two Families: Simple O(n²) vs. Clever O(n log n)
Every comparison-based sorting algorithm falls into one of two performance tiers. The simple tier — bubble, insertion, selection sort — is easy to write and understand but runs in O(n²) because each one, in its own way, compares every element to many others. The clever tier — merge sort and quicksort — uses a divide-and-conquer strategy to achieve O(n log n), the best general achievable complexity for comparison sorts.
The simple algorithms aren't obsolete — they're often faster in practice on small or nearly-sorted lists, and insertion sort in particular is used internally by many real-world sorting libraries for small sub-arrays.
💡 Memory Trick
BUBBLE: largest values 'bubble up' to the end with repeated adjacent swaps. SELECTION: repeatedly 'select' the minimum remaining value and place it. INSERTION: build a sorted section one card at a time, like sorting a hand of playing cards. MERGE: split all the way down, then merge sorted halves back together. QUICK: pick a pivot, and partition everything smaller to its left and larger to its right.
The Five Algorithms
How Each One Actually Works
1
Bubble Sort — O(n²)
Repeatedly step through the list, comparing each pair of adjacent elements and swapping them if they're out of order. After each full pass, the largest unsorted value has 'bubbled' to its correct position at the end. Simple but slow — rarely used in practice beyond teaching.
2
Selection Sort — O(n²)
Divide the list into a sorted section (front) and unsorted section (back). On each pass, find the minimum value in the unsorted section and swap it into the front of that section. Makes the fewest actual swaps of any simple sort, which matters when swaps are expensive.
3
Insertion Sort — O(n²), O(n) best case
Build a sorted section one element at a time by taking the next unsorted element and inserting it into its correct position within the already-sorted section, shifting larger elements right. Extremely fast on nearly-sorted data — it's O(n) if the list is already sorted or close to it.
4
Merge Sort — O(n log n), stable
Recursively split the list in half until each piece has one element, then merge pairs of sorted pieces back together in order. Guarantees O(n log n) in every case — best, worst, and average — but requires extra memory to hold the merged pieces.
5
Quicksort — O(n log n) average, O(n²) worst case
Pick a 'pivot' element, partition the list so everything smaller than the pivot ends up to its left and everything larger ends up to its right, then recursively sort each side. Fast in practice and sorts in-place (no extra memory), but a poorly chosen pivot on already-sorted data can degrade to O(n²).
Choosing One
Stability and When Each Wins
A sort is 'stable' if elements with equal keys keep their original relative order — this matters when sorting objects by one field while wanting to preserve prior ordering on another field (e.g., sorting a list already sorted by name, now by department, and wanting people within the same department to stay alphabetical). Merge sort and insertion sort are stable; standard quicksort and selection sort are not.
In real systems, quicksort is usually the practical default (fast, in-place), merge sort is preferred when stability or guaranteed worst-case performance matters (like external sorting on disk), and insertion sort is used for small sub-arrays inside hybrid algorithms because its low overhead wins at small n.
🖥️ Applied Scenario
You're sorting a list of 50,000 customer orders by timestamp, and a colleague suggests bubble sort because 'it's the one everyone learns first.'
1
You recognize bubble sort is O(n²), meaning 50,000 orders would require roughly 2.5 billion comparisons in the worst case — this would visibly hang the application.
2
You recall merge sort and quicksort are both O(n log n), meaning the same 50,000 orders require roughly 50,000 × 17 ≈ 850,000 operations — thousands of times fewer.
3
Because you need to preserve the original insertion order for orders with identical timestamps, you specifically choose merge sort for its stability guarantee rather than quicksort.
4
Conclusion: both complexity class and stability requirements — not just 'which sort do I remember' — drove the correct choice.
📌 Exam Application
Exam questions typically ask you to state the time complexity (best, average, worst case) of each sort, identify which are stable, and trace through a small example by hand showing the list after each pass or partition step. You may also be asked why quicksort's worst case is O(n²) — the answer is a poorly chosen pivot (e.g., always picking the first element on already-sorted data) causing maximally unbalanced partitions.
⚠️ Most Common Sorting Algorithms Mistakes
The most common mistake is assuming quicksort is always O(n log n) — its worst case is O(n²), which examiners love to test with sorted or reverse-sorted input as the trigger. Another common trap: confusing selection sort (selects minimum, fewest swaps) with insertion sort (builds sorted section by insertion, fewest comparisons on nearly-sorted data) — they sound similar but work in opposite directions.
✓ Quick Self-Test
Can you list all five sorts and state, from memory, their worst-case time complexity and whether each is stable? Can you explain why merge sort needs extra memory while quicksort typically doesn't?
Next Lesson
Algorithm Paradigms
→
← All Algorithms Lessons