Three different ways to put a list of numbers in order, each with the same job, but a completely different strategy. Watch each one think, step by step, then compare how much work each actually does.
Compare each pair of neighbours; swap them if they're in the wrong order. Repeat passes over the list until a whole pass makes no swaps, that's how it knows it's finished.
A loop inside a loop, where both depend on n, is the biggest tell for O(n²). For our 9-item list, the worst case is (9×8)/2 = 36 comparisons, exactly what the counter showed on a reversed list. That nested-loop shape is worth spotting on sight in any pseudocode you're given.
Build up a sorted section one element at a time. Take the next value, and slide it backwards past anything bigger until it finds its correct spot, like sorting playing cards in your hand.
Same nested-loop shape as bubble sort: for each of the n elements, the inner while-loop might shift it past almost all the others. Worst case (reversed list): also (9×8)/2 = 36 comparisons. But notice the best case, an already-sorted list needs only 8 comparisons, one per element, because the inner loop exits immediately every time. That's genuinely adaptive behaviour, not just an add-on optimisation.
This one's recursive, split the list in half, sort each half (by calling itself), then merge the two sorted halves back together. Watch the call stack: it's the exact same pattern as the recursion you've already met.
Merge sort halves the list every time it splits, and you can only halve 9 items about log₂(9) ≈ 3.17 times before reaching single elements (9 → 4/5 → 2/3 → 1). That's the "levels of splitting" you saw in the call stack. At every level, merging still touches all n items once. Total work ≈ n items × log₂(n) levels: that's where n log n comes from.
Also recursive, but instead of splitting down the middle, it picks a pivot and partitions the list around it: everything smaller goes left, everything bigger goes right. Do that recursively to each side and the whole list ends up sorted.
This version always picks the last element of the current range as the pivot (the simplest possible choice, called the Lomuto scheme). When the pivot happens to land roughly in the middle each time, the list roughly halves with every partition, giving O(n log n), the same shape as merge sort. But pick badly, over and over, and each partition only peels off one element, giving O(n²), see the surprising result below.
With this pivot strategy, an already-sorted list is the worst case, not the best, the opposite pattern from every other sort on this page. Every single partition only ever removes one element (the pivot itself never has anything smaller to swap with), so it degrades to the same O(n²) shape as bubble and insertion sort's worst case.
A sort is stable if two equal values keep their original relative order after sorting. This matters more than it sounds, imagine sorting exam results by score, where some students are tied: a stable sort keeps tied students in their original (say, alphabetical) order; an unstable one might shuffle them.
Notice 2b still comes before 2e, and 5a still comes before 5c, exactly as they were in the input. All three algorithms here are stable, because each one only swaps when a value is strictly greater than the next (never swapping on equality). Change that one comparison from > to >= and you'd break stability, even though the list would still end up correctly sorted by value.
Same 9-number list, four algorithms. Notice bubble sort and insertion sort both do very little work when the list is already almost sorted, but bubble sort's comparisons barely change on a reversed list, merge sort barely changes at all between cases, and quicksort does the exact opposite of the others.
| Case | Bubble compares | Bubble swaps | Insertion compares | Insertion shifts | Merge compares | Quicksort compares | Quicksort swaps |
|---|---|---|---|---|---|---|---|
| Typical (demo list) | 30 | 16 | 22 | 16 | 21 | 18 | 10 |
| Best case (already sorted) | 8 | 0 | 8 | 0 | 13 | 36 | 0 |
| Worst case (reversed) | 36 | 36 | 36 | 36 | 16 | 36 | 4 |
Merge sort's comparisons barely move between best and worst case, that consistency is exactly why it's rated O(n log n) rather than O(n²), regardless of the starting order. Quicksort (with this pivot strategy) is the outlier: its comparisons actually peak on the already-sorted case, 36, the same as its worst case, while every other algorithm here treats "already sorted" as easy.