Sorting Algorithms Visualized: Bubble to Radix Sort

The comparison-sort lower bound

A comparison sort decides ordering solely by comparing pairs of elements. There are n! possible orderings of n elements, and a binary decision tree distinguishing all of them needs height at least ⌈log₂(n!)⌉, which by Stirling's approximation is Θ(n log n). This is a hard information-theoretic floor: any comparison-based sorting algorithm requires at least Ω(n log n) comparisons in the worst case. Merge sort and heap sort achieve that bound in the worst case; quicksort achieves it only on average, degrading to O(n²) on adversarial input. A stable sort preserves the relative order of equal elements — sorting by last name should keep an already-earlier John Smith before a Jane Smith.

O(n²) sorts and divide-and-conquer

Insertion sort is O(n) on nearly-sorted data and the right choice for small arrays or online data arriving one item at a time. Merge sort splits the array in half, recursively sorts each half, then merges: T(n) = 2T(n/2) + O(n), giving guaranteed O(n log n) in the best, average and worst case, stable, but not in-place — it needs O(n) auxiliary space. Python's Timsort and Java's Arrays.sort use a bottom-up variant that merges pre-existing sorted runs, hitting O(n) on nearly-sorted input. Quicksort partitions around a pivot: O(n log n) average with a good pivot, O(n²) worst case on a sorted array with a bad one — mitigated by median-of-three pivot selection, random pivots, or Introsort's fallback to heapsort past a recursion-depth threshold (used in C++'s std::sort).

Algorithm    Best        Average     Worst       Space   Stable  In-place
Insertion    O(n)        O(n²)       O(n²)       O(1)    Yes     Yes
Merge        O(n log n)  O(n log n)  O(n log n)  O(n)    Yes     No
Quicksort    O(n log n)  O(n log n)  O(n²)       O(log n) No     Yes
Heap Sort    O(n log n)  O(n log n)  O(n log n)  O(1)    No      Yes
Counting     O(n+k)      O(n+k)      O(n+k)      O(k)    Yes     No
Radix (LSD)  O(dn)       O(dn)       O(dn)       O(n+k)  Yes     No

Heap sort and beating the comparison bound

Heap sort builds a binary max-heap in O(n) (Floyd's build-heap, not n individual inserts), then repeatedly extracts the maximum in O(log n) per step, guaranteeing O(n log n) worst case with O(1) extra space — but it's not stable, and its random access pattern makes it 2–5× slower than quicksort in practice due to cache misses. Algorithms that avoid comparisons entirely can escape the n log n floor: counting sort tallies occurrences over a known range [0,k] and computes prefix sums, O(n+k); radix sort applies a stable counting sort to each digit position from least to most significant, O(d·(n+k)), and is the workhorse of GPU and distributed sorting; bucket sort scatters uniformly distributed floats into n buckets, O(n) expected.

Frequently asked questions

Try it live

Everything above runs in your browser — open Sorting Algorithms Visualizer and race Bubble, Quick, Merge, Heap, Insertion and Selection sort side by side, tuning array size, speed and starting order. Nothing is installed, nothing is uploaded.