How do bubble sort, merge sort and quicksort compare?

Bubble sort works by stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order. It repeats this process until no more swaps are needed. While it is incredibly easy to understand, it is very inefficient. Its time complexity is $O(n^2)$, meaning that as the number of items ($n$) grows, the time it takes grows quadratically. You will rarely use this outside of learning the basics.

Merge sort is a "divide and conquer" algorithm. It cuts the list in half recursively until it reaches single elements, which are technically already sorted. Then, it merges those sub-lists back together in the correct order. The huge advantage is its guaranteed speed: it always runs in $O(n \log n)$ time, no matter what. The downside? It requires creating temporary arrays to hold the divided halves, meaning its space complexity is $O(n)$.

Quicksort also uses "divide and conquer," but it sorts in place. It chooses a "pivot" element and partitions the array so that everything smaller is to the left of the pivot and everything larger is to the right. It then recursively applies this to the left and right sections. On average, it runs in $O(n \log n)$ time and requires very little extra memory ($O(\log n)$ space). However, if it repeatedly picks a bad pivot (like the highest or lowest number), its worst-case time complexity drops to a sluggish $O(n^2)$.

A common mistake is assuming that because quicksort has a worse "worst-case" time than merge sort, it must be slower. In the real world, quicksort is almost always faster because its inner loops are highly optimized for computer architecture, and bad pivots are easily avoided by picking a random pivot. Students also mix up memory usage: remember that merge sort is the "memory hog" of the three.