Sorting Algorithms: Comparing Bubble, Quick, Merge & Heap

Comparison sorting has a hard floor

Any sorting algorithm that decides ordering purely by comparing pairs of elements — which covers every algorithm on this page — cannot beat O(n log n) comparisons in the worst case, for a clean information-theoretic reason: there are n! possible orderings of n elements, each comparison has only two outcomes, and distinguishing between n! possibilities needs at least log₂(n!) ≈ n·log₂(n) comparisons, by Stirling's approximation. That single bound is the yardstick every algorithm below is measured against — some reach it, some do not, and the ones that do not are not simply worse implementations of the same idea, they are fundamentally different trade-offs.

O(n squared): simple, and honestly usually wrong for the job

Bubble sort repeatedly walks the array swapping adjacent out-of-order pairs until nothing moves; insertion sort builds the sorted region one element at a time, inserting each new element into its correct place among the already-sorted prefix; selection sort repeatedly finds the minimum of the unsorted remainder and swaps it into place. All three are O(n²) in the worst case — roughly n²/2 comparisons for a million elements is 500 billion operations, hopelessly slow — and none should be used on large real data. Insertion sort earns a genuine exception: on nearly sorted data it runs close to O(n) because each new element needs very few swaps to reach its place, which is exactly why production sort implementations (Timsort, IntroSort) switch to insertion sort for small sub-arrays or nearly-sorted runs rather than recursing all the way down.

Merge sort: guaranteed n log n, at the cost of memory

Merge sort splits the array in half recursively down to single elements, then merges sorted halves back together in linear time per level:

mergeSort(arr):
  if len(arr) <= 1: return arr
  mid = len(arr) / 2
  left  = mergeSort(arr[:mid])
  right = mergeSort(arr[mid:])
  return merge(left, right)     // linear-time merge of two sorted arrays

Merge sort guarantees O(n log n) in every case — best, average and worst — and is stable (equal elements keep their original relative order, which matters when sorting records by one field while wanting ties broken by insertion order). Its cost is memory: the merge step needs O(n) auxiliary space, which is why in-place, memory-constrained contexts often reach for something else despite merge sort's clean worst-case guarantee.

Quicksort: usually fastest, occasionally terrible

Quicksort picks a pivot, partitions the array so everything smaller than the pivot lands left and everything larger lands right, and recurses on each side. Its average case is O(n log n) with excellent constants — in practice quicksort typically beats merge sort on random data because it sorts in place and has better cache locality — but its worst case is O(n²), which happens whenever the pivot choice consistently splits the array into a size-1 and a size-(n−1) partition instead of two roughly equal halves. A naive "always pick the first element" pivot strategy hits this worst case on already-sorted input, which is precisely the input real-world data most often looks like — the reason production quicksorts use randomised or median-of-three pivot selection instead.

Heap sort: quicksort's worst-case guarantee, without the extra memory

Heap sort first arranges the array into a binary max-heap (every parent node at least as large as its children, buildable in O(n) time), then repeatedly swaps the heap's root — always the current maximum — to the end of the unsorted region and re-heapifies what remains, in O(log n) per extraction. This gives a guaranteed O(n log n) worst case, in place, with no extra memory — strictly better worst-case behaviour than quicksort and less memory than merge sort — but it loses on real-world speed to quicksort because heap operations jump around the array non-sequentially, which is far less cache-friendly than quicksort's mostly-sequential partitioning.

What the bars and the tones are actually showing

On this page every algorithm sorts the same starting array of bar heights, with each comparison and swap mapped to a distinct audio tone via the Web Audio API, so slow O(n²) algorithms are audibly as well as visibly grinding through far more operations than merge sort or quicksort on identical input. Watching bubble sort's short-range adjacent swaps versus quicksort's long-range partition jumps versus merge sort's clean divide-and-conquer sweep makes the difference between these access patterns — not just their operation counts — directly visible, which a big-O notation on a page never quite communicates.

Frequently asked questions

Try it live

Everything above runs in your browser — open Sorting Algorithms and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.