Sorting Algorithms
Six ways to sort a list, and why your exam cares which one you pick. Watch comparisons and swaps in the lab, then see O(n²) and O(n log n) pull apart on bigger inputs.
- Count the comparisons and moves an algorithm makes, not just its Big-O
- Trace bubble, selection and insertion sort frame by frame
- Explain how divide and conquer reaches O(n log n)
- Say what stability means and when it matters
- Choose the right sort for a given constraint, or correctly choose the built-in
Finish first
Cost at a glance
- bubble
- O(n²) average, O(n) best
- selection
- O(n²) always
- insertion
- O(n²) average, O(n) best
- merge
- O(n log n), O(n) space
- quick
- O(n log n) average, O(n²) worst
- heap
- O(n log n), O(1) space
Topic contents
Lesson 1 of 4
Two operations, counted
Every comparison sort is built from two primitives: compare two elements, and move an element. Big-O usually counts comparisons, but moves matter just as much in practice, because writing to memory is often the expensive half. This is why two algorithms with the same O(n²) label can behave very differently on real data.
Run the lab on the same six values with each algorithm and read the counters. Selection sort makes the most comparisons and the fewest moves. Bubble sort makes many of both. Insertion sort's counts collapse when the data is already close to sorted. None of that is visible in the complexity class alone.
Sorting algorithms
Bubble, selection and insertion sort on the same data, with live comparison and move counters so the quadratic cost is measured rather than asserted.
Sorting algorithms
best O(n) · average O(n²) · swaps up to O(n²)Start
Bubble sort compares neighbours and swaps them when they are out of order. Each pass pushes the largest remaining value to the end, which is where the name comes from.
Lesson 2 of 4
The three quadratic sorts
Bubble sort repeatedly compares neighbours and swaps them when they are out of order, so the largest value bubbles to the end on each pass. It is the easiest to explain and the worst to use, but it has one virtue: if a full pass makes no swaps the data is sorted and it can stop, giving it an O(n) best case.
Selection sort scans the unsorted region for the smallest value and swaps it into place. Its comparison count is fixed at n(n-1)/2 no matter what the input looks like, so it has no best case, but it never makes more than n-1 swaps. That makes it the choice in the rare situation where writes are far more expensive than reads.
Insertion sort takes each element and walks it left into an already-sorted prefix, stopping as soon as it meets something no greater than itself. On nearly sorted data that stop happens immediately, so it approaches O(n). It is also stable and works well on tiny arrays, which is why built-in language sorts often switch to it for short runs.
Lesson 3 of 4
Divide and conquer: O(n log n)
Merge sort splits the array in half, sorts each half the same way, and merges the two sorted halves in one linear pass. The splitting depth is log₂ n and each level does O(n) work merging, which multiplies out to O(n log n). It is stable and its worst case is the same as its best, but it needs O(n) extra space for the merge.
Quicksort also partitions, but around a chosen pivot: values below the pivot to the left, above to the right, then recurse into each side. Its average is O(n log n) with excellent constants and no extra array, which is why it is usually the fastest in practice. Its worst case is O(n²) when the pivot choice is consistently terrible, which is why real implementations randomise or median-select the pivot.
Heap sort builds a heap and repeatedly extracts the maximum. It gives a guaranteed O(n log n) with O(1) extra space, but its memory access pattern jumps around, so it usually loses to quicksort on real hardware despite the identical complexity class.
No comparison sort can beat O(n log n) in the general case: there are n! possible orderings and each comparison rules out at most half of them, so log₂(n!) comparisons are needed, which grows as n log n. Sorts that do better, such as counting or radix sort, buy that speed by not comparing at all and instead assuming something about the keys.
Lesson 4 of 4
What to actually do
Use the language's built-in sort. It is not laziness: `Array.prototype.sort` in V8 and Python's `sorted` both use Timsort, a hybrid that finds already-ordered runs, sorts short runs with insertion sort and merges the rest. It is stable, it is O(n log n) worst case, and it beats hand-written sorts on real data because real data is rarely random.
Two things you still have to get right yourself. First, the comparator: in JavaScript, `[10, 9, 1].sort()` gives `[1, 10, 9]` because the default converts values to strings, so numbers need `(a, b) => a - b`. Second, stability, which matters whenever you sort by one key after another. Sort by name and then by department with a stable sort, and rows within a department stay alphabetical; with an unstable sort that order is silently lost.
Worked examples
Read the code, then change it
Copy any example into the playground and break it on purpose. That is the fastest way to learn what each line is holding up.
function bubbleSort(input) {
const a = [...input];
let comparisons = 0;
let swaps = 0;
for (let pass = 0; pass < a.length - 1; pass += 1) {
let swapped = false;
for (let i = 0; i < a.length - 1 - pass; i += 1) {
comparisons += 1;
if (a[i] > a[i + 1]) {
[a[i], a[i + 1]] = [a[i + 1], a[i]];
swaps += 1;
swapped = true;
}
}
if (!swapped) break; // already sorted: the O(n) best case
}
return { sorted: a, comparisons, swaps };
}
const random = [42, 8, 15, 4, 23, 16];
const sortedAlready = [4, 8, 15, 16, 23, 42];
const reversed = [42, 23, 16, 15, 8, 4];
for (const [name, data] of [['random', random], ['sorted', sortedAlready], ['reversed', reversed]]) {
const { comparisons, swaps } = bubbleSort(data);
console.log(name.padEnd(9), comparisons, 'comparisons', swaps, 'swaps');
}const numbers = [10, 9, 1, 100, 25];
console.log([...numbers].sort()); // [1, 10, 100, 25, 9] is string order!
console.log([...numbers].sort((a, b) => a - b)); // [1, 9, 10, 25, 100]
// Stability: sort by score, then by name, and equal scores stay alphabetical.
const players = [
{ name: 'Asha', score: 8 },
{ name: 'Bilal', score: 9 },
{ name: 'Chen', score: 8 },
];
const byName = [...players].sort((a, b) => a.name.localeCompare(b.name));
const byScore = byName.sort((a, b) => b.score - a.score);
console.log(byScore.map((p) => p.name + ':' + p.score).join(', '));Practice
Work these out yourself
No answer key here on purpose: these are the questions worth thinking through before you move on. Open one and work it out.
0/5 attemptedAssessment
Check your understanding
Answer each question, then read the explanation. That is where the learning is.
Finished this topic?
0 of 4 lessons marked done. Marking the topic complete ticks the rest.