Sorting Algorithms Compared: Bubble vs Merge vs Quick

Learn With Examples · Computer Science

Three ways to put a list in order. One you’d never ship, one you can trust with anything, and one that beats them both — until the day it doesn’t. Here’s how each actually works, watched step by step.

Hand a deck of shuffled cards to three people and watch what they do. The first goes along the row swapping any two neighbours in the wrong order, over and over, until a full pass changes nothing. The second splits the deck in half, sorts each half, then merges the two sorted piles by repeatedly taking the smaller of the two top cards. The third picks one card, throws everything smaller to the left and everything bigger to the right, then repeats on each side.

Those three people just performed bubble sort, merge sort and quicksort. No pseudocode required — the ideas are that physical. What separates them is not cleverness but how many comparisons they need, and that difference explodes as the deck gets bigger.

This article walks through all three step by step, then answers the question that actually matters at work: which one do you reach for, and when does the popular choice betray you?

The 20-second version

Bubble sort compares neighbours and swaps them. Beautifully simple, quadratic time, useless beyond a few hundred items. Learn it, then never ship it.

Merge sort splits, sorts, and merges. Reliably O(n log n) in every case and stable, but needs extra memory the size of your list.

Quicksort partitions around a pivot. Usually the fastest of the three in practice and sorts in place, but a bad pivot can drag it down to quadratic.

Step through all three

Pick an algorithm, then tap through the numbered steps. Cyan marks a comparison, pink a value being moved, amber quicksort’s pivot. All three start from the same six numbers — count how many steps each one needs.

Bubble sort: the one everyone learns first

Bubble sort does exactly one thing: walk the list, compare each pair of neighbours, swap them if they’re out of order. Repeat until a full pass produces no swaps at all. Large values “bubble” to the end one position per pass, which is where the name comes from.

Sort [5, 1, 4, 2] by hand:

Pass	Comparison	List after
1	5 vs 1 → swap	[1, 5, 4, 2]
1	5 vs 4 → swap	[1, 4, 5, 2]
1	5 vs 2 → swap	[1, 4, 2, 5]
2	1 vs 4 → keep	[1, 4, 2, 5]
2	4 vs 2 → swap	[1, 2, 4, 5]
3	no swaps made	[1, 2, 4, 5] ✓

// bubble sort with the early-exit optimisation
function bubbleSort(a) {
  for (let i = 0; i < a.length - 1; i++) {
    let swapped = false;
    for (let j = 0; j < a.length - 1 - i; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
        swapped = true;
      }
    }
    if (!swapped) break;   // already sorted, stop early
  }
  return a;
}

The cost is brutal. Every pass compares nearly every pair, and you need close to n passes, so the work grows with n². Ten items cost about 45 comparisons. A thousand items cost roughly half a million. Ten thousand cost fifty million. You can feel that in a browser tab.

The one situation where bubble sort isn’t embarrassing is nearly sorted data. With the early-exit check above, an already-sorted list is verified in a single pass of n-1 comparisons — that’s O(n), better than merge sort’s best case. If you have a list where one element occasionally drifts out of place, a bubble pass is a perfectly reasonable repair. That’s a narrow niche, and insertion sort usually fills it better, but it’s real.

Why teach it at all, then? Because it makes the shape of the problem visible. Once you’ve watched bubble sort waste 20 comparisons re-checking pairs it already knows are fine, the motivation behind divide-and-conquer stops being abstract. It’s the algorithm you learn in order to want a better one.

Merge sort: split, sort, stitch

Merge sort refuses to compare distant items at all. Instead it breaks the list in half, again and again, until every piece has a single element — and a single element is sorted by definition. Then it walks back up, merging pairs of sorted pieces.

The merge step is where the magic sits, and it’s the part worth understanding physically. You have two sorted piles face up. Look at the top card of each. Take the smaller one. Repeat. Because both piles are sorted, the smallest remaining card is always one of the two you’re looking at — you never search, you never backtrack.

Merging [1, 4] and [2, 3]:

Left pile	Right pile	Compare	Output
[1, 4]	[2, 3]	1 vs 2 → take 1	[1]
[4]	[2, 3]	4 vs 2 → take 2	[1, 2]
[4]	[3]	4 vs 3 → take 3	[1, 2, 3]
[4]	[ ]	right empty → copy 4	[1, 2, 3, 4]

Count the levels: halving a list of 1,000 takes about 10 splits to reach single items, because 2¹⁰ is 1,024. Each level does roughly n comparison work to merge everything back. Ten levels × a thousand items ≈ 10,000 operations, against bubble sort’s half a million. That’s the entire argument for O(n log n), and it’s why merge sort’s worst case, best case and average case are all the same — the splitting doesn’t care what the data looks like.

Two properties make merge sort the professional’s safe choice:

It’s stable

Equal items keep their original relative order. Sort orders by date, then by customer, and the date order survives inside each customer. Quicksort does not promise this.

It’s predictable

No input can make it slow. For latency-sensitive systems, a guaranteed ceiling beats a lower average with a nasty tail.

It works off-disk

Merging needs only the front of each pile, so you can sort a 500 GB file with 8 GB of RAM. This is how external sorting works.

It costs memory

The standard version needs a scratch array as big as the input. On memory-tight systems, that’s the dealbreaker.

Quicksort: pick a pivot, throw everything to one side

Quicksort also divides and conquers, but it partitions before recursing rather than after. Choose one element as the pivot. Rearrange the list so everything smaller sits left of it and everything larger sits right. The pivot is now in its final position, permanently. Then repeat on the left chunk and the right chunk.

Take [7, 2, 9, 4, 5] with 5 as the pivot. Walk the rest: 7 is bigger (right), 2 is smaller (left), 9 is bigger (right), 4 is smaller (left). You get [2, 4] 5 [7, 9]. One pass, and 5 is done forever. Now solve the two small pieces the same way.

// quicksort, Lomuto partition scheme
function quickSort(a, lo = 0, hi = a.length - 1) {
  if (lo >= hi) return a;
  const pivot = a[hi];
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (a[j] < pivot) {
      [a[i], a[j]] = [a[j], a[i]];
      i++;
    }
  }
  [a[i], a[hi]] = [a[hi], a[i]];   // pivot into place
  quickSort(a, lo, i - 1);
  quickSort(a, i + 1, hi);
  return a;
}

On average the pivot lands somewhere near the middle, the problem halves each time, and you get O(n log n) — typically with a smaller constant factor than merge sort, because quicksort swaps within the original array instead of copying into a scratch one. Fewer memory writes, better cache behaviour, faster in the real world.

The trap. Suppose you always pick the last element as pivot, and the list is already sorted. Every pivot is the largest remaining value, so one side gets everything and the other gets nothing. You’ve turned O(n log n) into O(n²) — and the input that triggers it is the most common input in the world: data that’s already in order. Real implementations dodge this by picking a random pivot, or the median of the first, middle and last elements.

Race them on the same data

Same shuffled array, three algorithms, one operation per tick. This isn’t a wall-clock benchmark — it’s an operations count, which is what the big-O notation is actually measuring.

Head-to-head race

tick to start

Run the race / reset

Bubble ~1,800 comparisons

Merge ~300 comparisons

Quick ~250 comparisons

Each bar advances at a speed proportional to the work its algorithm really does on a shuffled 60-item list. Quick and merge finish while bubble sort is still grinding through its second pass.

On random data quicksort usually finishes first, merge close behind, bubble far back. Hand all three an already-sorted list, though, and the ranking inverts completely: bubble sort exits after a single clean pass, while quicksort with a naive last-element pivot collapses into its worst case. Same three algorithms, opposite result, purely because the input changed shape.

Big-O tells you how an algorithm behaves as data grows. It doesn’t tell you which one wins on your data. Only the shape of your input decides that.

The numbers, side by side

	Bubble	Merge	Quick
Best case	O(n)	O(n log n)	O(n log n)
Average	O(n²)	O(n log n)	O(n log n)
Worst case	O(n²)	O(n log n)	O(n²)
Extra memory	O(1)	O(n)	O(log n)
Stable?	Yes	Yes	No
In place?	Yes	No	Yes
Use it when	Teaching, or tiny nearly-sorted lists	You need guarantees, stability, or external sorting	You want raw speed on in-memory data

Those symbols get abstract fast, so put real numbers on them. Pick a list size and watch the gap between quadratic and logarithmic growth open up.

How bad does n² get?

pick a list size

10 items100 items1,000 items100,000 items

45Bubble ops (n²)

33Merge / quick ops

1.4×Times more work

instantBubble time est.

5,000Bubble ops (n²)

664Merge / quick ops

7.5×Times more work

under 1 msBubble time est.

500,000Bubble ops (n²)

9,966Merge / quick ops

50×Times more work

5 msBubble time est.

5 billionBubble ops (n²)

1,660,964Merge / quick ops

3,010×Times more work

50 secondsBubble time est.

Notice how the ratio behaves. At 100 items bubble sort does around 15 times more work — annoying, survivable. At 100,000 items it does over 3,000 times more. That is the difference between a page that renders instantly and one that hangs the browser for a minute. Complexity classes don’t matter much at small scale and matter enormously at large scale, which is exactly why beginners under-rate them.

So which one do you actually use?

Honest answer for day-to-day work: call your language’s built-in sort. It’s been tuned by people who do nothing else. But knowing what’s under it tells you when to override it.

Sorting objects by two fields

You need stability — merge sort, or a built-in that guarantees it. Sort by the secondary key first, then the primary.

Big array, memory is tight

Quicksort. In-place, cache-friendly, only recursion stack overhead. Just randomise the pivot.

Data bigger than RAM

Merge sort. It’s the only one of the three that sorts chunks on disk and merges streams.

Worst case must be bounded

Merge sort. Real-time and latency-critical systems care about the ceiling, not the average.

Fewer than ~20 items

Use insertion sort. Its overhead is so low it beats the clever algorithms at small sizes — which is why real implementations switch to it below a threshold.

Explaining sorting to someone

Bubble sort, once. Then show them the step-through above and let the operation count make the argument.

What most standard libraries actually run is a hybrid. Introsort starts as quicksort, counts its recursion depth, and switches to heapsort if the pivots are going badly — giving quicksort’s speed with a guaranteed O(n log n) ceiling. Timsort, used in Python and Java for objects, is merge sort that detects runs of already-ordered data and exploits them, which makes it startlingly fast on the semi-sorted data that real applications produce. Both are engineering answers to the trade-offs on this page.

Check yourself

Five questions. Open each one to check yourself — the correct option is marked.

1. Why is merge sort’s worst case the same as its best case?

It checks the data first
The splitting is fixed and doesn’t depend on the values
It uses extra memory
It’s stable

Merge sort always halves the list, whatever’s in it. The number of levels is fixed at log₂n, so no input can make it slow.

2. Which input makes naive quicksort hit its worst case?

Random data
Data with many duplicates only
Already-sorted data with a last-element pivot
Very short lists

Every pivot becomes the largest remaining value, so one partition gets everything. The fix is a random or median-of-three pivot.

3. What does “stable” mean for a sorting algorithm?

Equal items keep their original relative order
It never crashes
It always takes the same time
It uses no extra memory

Stability lets you sort by one field, then another, and keep the first ordering inside groups. Quicksort doesn’t guarantee it.

4. Roughly how many comparisons does bubble sort need for 1,000 items?

About 1,000
About 10,000
About 500,000
About 1,000,000

Roughly n²/2 — half a million. Merge sort handles the same list in about 10,000.

5. You must sort a 400 GB log file on a machine with 16 GB of RAM. Which approach?

Quicksort, it’s in place
Merge sort, sorting chunks then merging streams
Bubble sort, it uses no extra memory
None can do it

External merge sort only needs the front of each sorted run in memory at a time — the classic solution to sorting more data than you can hold.

Frequently asked questions

Which sorting algorithm is fastest?

For general in-memory data, quicksort is usually fastest in practice because it sorts in place with excellent cache behaviour. Merge sort is faster in the worst case, since quicksort can degrade to O(n²) with bad pivots. Bubble sort is slowest by a wide margin at any meaningful size.

Is bubble sort ever useful in real code?

Rarely, but not never. On a list that’s already nearly sorted, the early-exit version runs in O(n) and is trivial to write and verify. For anything else, insertion sort does the same job better and your language’s built-in sort beats both.

Why does quicksort beat merge sort if merge sort has a better worst case?

Constant factors. Quicksort swaps elements inside the original array; merge sort copies into a scratch array and back on every level. Fewer memory writes and better cache locality mean quicksort typically wins on wall-clock time even when both are O(n log n).

What does O(n log n) actually mean in plain terms?

The work grows a little faster than the list size, but nowhere near as fast as squaring it. Double the items and you do slightly more than double the work — whereas O(n²) means doubling the items quadruples the work. That gap is what makes large-scale sorting feasible at all.

Which sort do Python, Java and JavaScript use?

Python uses Timsort, a merge sort variant that detects existing sorted runs. Java uses Timsort for objects and a dual-pivot quicksort for primitives. Most JavaScript engines use Timsort-style stable sorts for Array.sort(). All three are hybrids built from the ideas on this page.

The takeaway

Bubble sort compares neighbours and pays for it quadratically. Merge sort splits the problem into halves whose cost adds up to n log n, every single time, at the price of extra memory. Quicksort partitions around a pivot and is usually the fastest of the three — as long as the pivot is chosen sensibly.

The deeper lesson isn’t which one wins. It’s that the same task can be organised in ways whose costs diverge by a factor of thousands, and that the winning approach depends on the shape of your data, not on the elegance of the code. Step back through the three walkthroughs above and count what each one needed on the very same six numbers — then imagine those gaps at a million items. That is the thing worth remembering.

bubble sortmerge sortquicksortbig-Oalgorithmsdata structures