Sorting Algorithms — Bubble, Merge, Quick Sort Compared

A sorting algorithm rearranges the same items into order, such as smallest to largest. If you want the short answer first, bubble sort is simple but usually too slow for big lists, merge sort gives reliable $O(n \log n)$ performance, and quick sort is often fast in practice when its partitions stay reasonably balanced.

The right question is not "which sort is best?" but "best under what condition?" Bubble sort teaches local swaps, merge sort shows divide-and-conquer clearly, and quick sort shows why average-case speed can be strong even without a worst-case guarantee.

What Sorting Algorithms Do

Given a list such as $[5, 1, 4, 2]$, the algorithm should return the same values in order:

$$[1, 2, 4, 5]$$

That sounds simple, but different algorithms reach that result in very different ways. The main differences are:

• how they move items
• how many comparisons or swaps they tend to use
• how much extra memory they need
• how sensitive they are to bad input patterns

Bubble Sort: Repeated Neighbor Swaps

Bubble sort walks through the list and swaps adjacent items that are out of order. After one full pass, the largest unsorted item has "bubbled" to the end.

On $[5, 1, 4, 2]$, the first pass looks like this:

$$[5, 1, 4, 2] \to [1, 5, 4, 2] \to [1, 4, 5, 2] \to [1, 4, 2, 5]$$

Then it repeats on the remaining unsorted part until no swaps are needed.

Bubble sort is mainly useful for learning. In general, it has $O(n^2)$ time complexity, so the number of comparisons grows quickly as the list gets larger. For small classroom examples that is fine. For serious sorting work, it is usually not the right choice.

Merge Sort: Split, Sort, Then Merge

Merge sort uses a divide-and-conquer idea. It splits the list into smaller parts, sorts those parts, and then merges the sorted pieces back together.

For $[5, 1, 4, 2]$, one clean view is:

$$[5, 1, 4, 2] \to [5, 1] + [4, 2]$$

Sort each half:

$$[5, 1] \to [1, 5], \qquad [4, 2] \to [2, 4]$$

Then merge the two sorted halves:

$$[1, 5] + [2, 4] \to [1, 2, 4, 5]$$

The main strength of merge sort is predictability. Its running time is $O(n \log n)$ in the usual analysis, not just on average. The main cost is memory: common array-based implementations use extra space while merging.

Quick Sort: Partition Around A Pivot

Quick sort also uses divide-and-conquer, but in a different way. It picks a pivot, places smaller items on one side and larger items on the other, and then sorts the two sides recursively.

Using pivot $4$ on $[5, 1, 4, 2]$, one possible partition is:

$$[1, 2] \;|\; 4 \;|\; [5]$$

Now the left and right parts are much smaller, so sorting finishes quickly.

Quick sort is often fast in practice because many implementations partition in place and reduce the problem quickly when the pivot splits the list fairly well. But that condition matters. If the pivot choices are repeatedly poor, such as producing one tiny side and one almost-full side again and again, the worst case becomes $O(n^2)$.

Bubble Sort vs Merge Sort vs Quick Sort

Algorithm	Core idea	Typical time	Worst-case time	Extra memory
Bubble sort	Repeated adjacent swaps	$O(n^2)$	$O(n^2)$	Low
Merge sort	Split, sort halves, merge	$O(n \log n)$	$O(n \log n)$	Higher in common array implementations
Quick sort	Partition around a pivot	Often $O(n \log n)$	$O(n^2)$	Often lower than merge sort

If you want one practical takeaway, it is this: bubble sort is a teaching algorithm, merge sort is the steady predictable option, and quick sort is often the practical speed choice when the implementation handles pivots well.

One Worked Example On The Same List

Use the same list:

$$[5, 1, 4, 2]$$

Bubble sort keeps fixing local mistakes. It does not "see" the whole structure, so it may need many passes.

Merge sort first breaks the problem into smaller sorted pieces, then combines them. That structure is why its performance stays reliable as the list grows.

Quick sort tries to make one strong split early. If the split is balanced enough, the rest of the work shrinks fast.

This is why students often remember the complexity numbers better after watching one list move through each method. The numbers are not arbitrary labels. They reflect how the algorithm reduces disorder.

Common Mistakes When Comparing Sorting Algorithms

Assuming Quick Sort Is Always Faster

Quick sort is often fast in practice, not guaranteed fastest in every case. Bad pivot behavior can hurt it badly.

Treating $O(n \log n)$ Algorithms As Identical

Merge sort and quick sort can share the same average growth rate without behaving the same way in memory use, worst-case guarantees, or implementation details.

Using Bubble Sort Because It Is Easy To Code

Ease of coding is not the same as suitability. For tiny demos bubble sort is fine. For larger real inputs, it usually does unnecessary work.

Forgetting The Input Model

These comparisons usually assume comparison-based sorting on general inputs. If the data has special structure, non-comparison sorts such as counting sort may change the decision completely.

When Each Sorting Algorithm Is Used

Bubble sort is mostly used for teaching, tracing, and very small examples where clarity matters more than performance.

Merge sort is used when consistent $O(n \log n)$ behavior matters and extra memory is acceptable. It is also a natural fit for linked lists and for situations where stable sorting matters, depending on the implementation.

Quick sort is used when practical speed is important and the implementation has a good pivot strategy or fallback protections. Many standard-library sorting strategies use quick-sort ideas together with safeguards rather than a naive textbook version.

A Fast Way To Remember The Difference

Remember them by motion:

• bubble sort fixes neighbors
• merge sort builds sorted halves
• quick sort splits around a pivot

That mental picture is more useful than memorizing three names and three formulas.

Try Your Own Version

Take the list $[7, 3, 6, 1]$ and trace one pass of bubble sort, one split-and-merge cycle of merge sort, and one pivot partition for quick sort. If you can explain why the list changes differently in each case, the concept has clicked.