Why is merge sort faster than bubble sort?
Bubble sort compares and swaps neighbors over and over, which takes about n²/2 comparisons for n items in the worst case. Merge sort splits the list in half, sorts each half and merges them, which takes about n log₂ n comparisons, so it scales far better as lists grow.
How bubble sort works
Bubble sort walks through the list comparing each pair of neighbors and swapping them if they are out of order. After the first pass the largest item has bubbled to the end; after the second, the two largest are in place; and so on.
Sort [5, 1, 4, 2, 8]. Pass 1 swaps 5 and 1, then 5 and 4, then 5 and 2, and leaves 5 and 8 alone: [1, 4, 2, 5, 8]. Pass 2 swaps 4 and 2: [1, 2, 4, 5, 8]. Pass 3 makes no swaps, so a version that stops early knows the list is sorted.
In the worst case, a list in reverse order, bubble sort makes n(n − 1)/2 comparisons. For 1,000 items that is 499,500.
How merge sort works
Merge sort is recursive. It splits the list in half, sorts each half, and merges the two sorted halves by repeatedly taking the smaller front item. The base case is a list of one item, which is already sorted.
Merging two sorted lists with m items in total takes at most m − 1 comparisons. A list can be halved only about log₂ n times, and each level of merging handles all n items, so the total is about n log₂ n. For 8 items: four merges of pairs (4 comparisons), two merges of 2 + 2 (up to 6) and one merge of 4 + 4 (up to 7), at most 17 in all, against 28 for bubble sort's worst case. For 1,000 items, about 10,000 against 499,500. For a million, about 20 million against about 500 billion.
Trade-offs exams ask about
- Big O: bubble sort is O(n²) in the worst and average cases; merge sort is O(n log n) in every case.
- Memory: the usual array version of merge sort needs O(n) extra space to merge into. Bubble sort sorts in place.
- Nearly sorted input: bubble sort with an early exit takes only one pass, O(n), on a list that is already sorted.
- Stability: both keep equal items in their original order when written the standard way.
- Big O describes growth, not speed on one run. On a list of ten items, the difference hardly matters.
Watching both run
Ask Isotoon "Why is merge sort faster than bubble sort?" and you get a short narrated animation. A clear one runs both algorithms on the same eight bars side by side, with a comparison counter under each, so you watch bubble sort grind through neighbor swaps while merge sort splits and merges in three levels. More is on computer science.
Questions
- Is bubble sort ever better than merge sort?
- On very small lists or lists that are already nearly sorted, bubble sort with an early exit can finish quickly and needs no extra memory. For anything large, merge sort wins by a wide margin.
- Why is merge sort O(n log n)?
- The list can be split in half about log base 2 of n times before every piece has one item, and merging at each level touches all n items once. That is n work for each of about log n levels.