Sorting Algorithms
Watch bubble, selection, insertion, merge, quick and heap sort run on your own numbers, step by step with the counts.
Θ(n) best, Θ(n²) average, Θ(n²) worst
each swap exchanges two elements
stable — equal values keep their original order
| 0 | 42719388256114 | Starting array. | 0c |
| 1 | 74219388256114 | 42 > 7, so they swap. | 1c |
| 2 | 71942388256114 | 42 > 19, so they swap. | 2c |
| 3 | 71934288256114 | 42 > 3, so they swap. | 3c |
| 4 | 71934288256114 | 42 ≤ 88, already in order. | 4c |
| 5 | 71934225886114 | 88 > 25, so they swap. | 5c |
| 6 | 71934225618814 | 88 > 61, so they swap. | 6c |
| 7 | 71934225611488 | 88 > 14, so they swap. | 7c |
| 8 | 71934225611488 | 7 ≤ 19, already in order. | 8c |
| 9 | 73194225611488 | 19 > 3, so they swap. | 9c |
| 10 | 73194225611488 | 19 ≤ 42, already in order. | 10c |
| 11 | 73192542611488 | 42 > 25, so they swap. | 11c |
| 12 | 73192542611488 | 42 ≤ 61, already in order. | 12c |
| 13 | 73192542146188 | 61 > 14, so they swap. | 13c |
| 14 | 37192542146188 | 7 > 3, so they swap. | 14c |
| 15 | 37192542146188 | 7 ≤ 19, already in order. | 15c |
| 16 | 37192542146188 | 19 ≤ 25, already in order. | 16c |
| 17 | 37192542146188 | 25 ≤ 42, already in order. | 17c |
| 18 | 37192514426188 | 42 > 14, so they swap. | 18c |
| 19 | 37192514426188 | 3 ≤ 7, already in order. | 19c |
| 20 | 37192514426188 | 7 ≤ 19, already in order. | 20c |
| 21 | 37192514426188 | 19 ≤ 25, already in order. | 21c |
| 22 | 37191425426188 | 25 > 14, so they swap. | 22c |
| 23 | 37191425426188 | 3 ≤ 7, already in order. | 23c |
| 24 | 37191425426188 | 7 ≤ 19, already in order. | 24c |
| 25 | 37141925426188 | 19 > 14, so they swap. | 25c |
| 26 | 37141925426188 | 3 ≤ 7, already in order. | 26c |
| 27 | 37141925426188 | 7 ≤ 14, already in order. | 27c |
| 28 | 37141925426188 | A whole pass with no swap, so the array is sorted and the rest of the passes are skipped. | 27c |
Highlighted cells are the ones the step touched; green cells are in their final place.
| Algorithm | Comparisons | Moves | Worst case | Stable |
|---|---|---|---|---|
| Bubble sort | 27 | 13 | Θ(n²) | yes |
| Selection sort | 28 | 5 | Θ(n²) | no |
| Insertion sort | 18 | 13 | Θ(n²) | yes |
| Merge sort | 16 | 24 | Θ(n log n) | yes |
| Quicksort | 16 | 7 | Θ(n²) | no |
| Heapsort | 25 | 19 | Θ(n log n) | no |
Bubble, selection and insertion sort all take Θ(n²) comparisons in the worst case; merge, quick and heap sort take Θ(n log n). The counts above are the real ones for your input, so the difference between best and worst case shows up directly.
The three quadratic sorts are not interchangeable
Textbooks group bubble, selection and insertion sort together as the slow ones, which hides what separates them. Run all three on eight already-sorted values and the difference is stark: insertion and bubble sort finish in 7 comparisons and no moves at all, while selection sort still does 28 comparisons. Selection sort cannot take advantage of order, because finding the minimum of the remaining part always means looking at all of it. Its comparison count is exactly n(n−1)/2 for every input that exists.
That rigidity buys one thing. Selection sort makes at most n − 1 swaps, where bubble sort makes one swap per inversion — on eight reversed values, 28 of them. If moving an element is expensive and comparing is cheap, selection sort is the one you want, and it is the reason it survives in contexts where writes cost far more than reads.
What the move counts actually measure
Both bubble sort’s swaps and insertion sort’s shifts equal the number of inversions in the input — the count of pairs that start out in the wrong order. That is not an approximation, it is exact, and it is the cleanest way to see why nearly sorted data is cheap for them: few inversions, few moves. Merge sort ignores this entirely. It moves every element once per level of recursion whatever the input, so its move count is the same for sorted, reversed and random data, and only its comparison count varies.
two exact identities, not bounds — the tool checks them on whatever you enter
- 1 Write the array out once per pass, not once per swap. An exam answer wants the state after each outer-loop pass. Tracing every inner comparison fills a page and hides the structure.
- 2 Mark which end is finished. Bubble sort settles the largest value at the right on each pass; selection and insertion sort build a sorted run from the left.
- 3 For insertion sort, remember the held value. The element being inserted is lifted into a variable first, so mid-pass the array genuinely has a duplicate and a stale slot.
- 4 For merge and quicksort, draw the recursion as a tree. The work happens on the way back up for merge sort, and on the way down for quicksort — that is the whole difference between them.
- 5 Count comparisons separately from moves. They answer different questions, and an algorithm can be good at one and bad at the other.
The six algorithms compared
Space is the extra memory beyond the array itself. Stable means equal values keep their original relative order.
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble sort | Θ(n) | Θ(n²) | Θ(n²) | O(1) | Yes |
| Selection sort | Θ(n²) | Θ(n²) | Θ(n²) | O(1) | No |
| Insertion sort | Θ(n) | Θ(n²) | Θ(n²) | O(1) | Yes |
| Merge sort | Θ(n log n) | Θ(n log n) | Θ(n log n) | O(n) | Yes |
| Quicksort | Θ(n log n) | Θ(n log n) | Θ(n²) | O(log n) | No |
| Heapsort | Θ(n log n) | Θ(n log n) | Θ(n log n) | O(1) | No |
Why quicksort wins in practice despite the worst case
On paper heapsort looks strictly better than quicksort: the same average behaviour, a guaranteed Θ(n log n) worst case instead of a quadratic one, and constant extra space instead of a recursion stack. In practice quicksort is usually faster, because its inner loop is a single forward scan over contiguous memory while heapsort jumps between indices i, 2i+1 and 2i+2 — a pattern that defeats the cache badly at any realistic size. The comparison counts above are equal; the time is not.
The quadratic worst case is real but avoidable. Lomuto partitioning with the last element as pivot, which is what the trace here shows, degrades to Θ(n²) on already-sorted input — the counts will show it. Choosing the pivot at random, or as the median of three, makes that case vanishingly unlikely. Production sorts go further: introsort watches its own recursion depth and switches to heapsort if the partitioning is going badly, so it keeps quicksort’s speed and heapsort’s guarantee.
Stability is the property that decides the rest. If you sort a list of records by date and then by name, a stable sort leaves same-name records still in date order, and an unstable one scrambles them. Bubble, insertion and merge sort are stable because they only ever move an element past something strictly greater; selection, quick and heap sort exchange distant elements and lose the original order of ties. This is why Python and Java use merge-sort variants for objects — Timsort and its relatives — and reserve quicksort for primitives, where equal values are indistinguishable and stability means nothing.