Everything compared
Sorting Algorithms Comparison
Every sorting algorithm at a glance: best, average, and worst case time, space complexity, stability, and in-place behavior. Click any row or column to focus it, then read the decision guide below the table.
TL;DR The short version
Three algorithms hold O(n log n): Merge Sort, Quick Sort, and Heap Sort. Radical differences hide in the details. Merge Sort needs O(n) memory but is stable. Quick Sort uses almost no extra memory but can degrade to O(n^2). Heap Sort needs no memory and never degrades, but is not stable. Everything else is O(n^2) and only worth using on tiny, nearly sorted, or memory-constrained inputs. Radix Sort is the outlier: non-comparison, stable, and linear for bounded integers.
01The full comparison table
Click a row to spotlight that algorithm, or click a column header to spotlight that property.
| Algorithm | Best | Average | Worst | Space | Stable | In-place | Type |
|---|---|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes | Yes | Comparison |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) | O(1) | No | Yes | Comparison |
| Insertion Sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes | Yes | Comparison |
| Shell Sort | O(n log n) | O(n^1.25) | O(n^2) | O(1) | No | Yes | Comparison |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No | Comparison |
| Quick Sort | O(n log n) | O(n log n) | O(n^2) | O(log n) | No | Yes | Comparison |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Yes | Comparison |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n + k) | Yes | No | Non-comparison |
O(n log n) means efficient and scalable. O(n^2) means simple but slow past roughly 10,000 items. Space and in-place are the hidden costs that decide real systems.
02The complexity classes on a chart
The same Big O numbers, drawn for n from 1 to 100. Efficient sorts stay low and flat; O(n^2) sorts break away early.
03Key definitions
Best, average, and worst case
Best is the input that finishes fastest, usually already sorted. Worst is the slowest, usually reversed. Average is the expected cost over typical inputs. Quick Sort is O(n log n) average but O(n^2) worst.
In-place
Sorts using a constant O(1) amount of extra memory. Great when memory is tight. Merge Sort and Radix Sort are the exceptions because they build a copy buffer.
Stable
Preserves the original relative order of equal keys. Required when sorting records that already carry a secondary order. Merge, Insertion, and Bubble are stable; Quick and Heap are not.
Comparison vs non-comparison
Comparison sorts order by comparing keys and stop at O(n log n). Radix Sort buckets values by digit and reaches O(nk), but only works on bounded-key data such as integers.
04Which algorithm wins for your case
The practical rules behind the decision panel on the guide page.
Insertion Sort
Runs in O(n) on sorted data with zero overhead. The linear scan wins by a mile.
Quick Sort
Fewest comparisons and moves in practice at O(n log n) average.
Merge or Heap Sort
Both hold O(n log n) in every case. Merge is stable, Heap is memory-free.
Heap Sort
The strongest in-place O(n log n) sort. Merge Sort cannot compete on memory.
Radix Sort
Linear O(nk), stable, and unbeatable when the key width is small.
Bubble Sort
Awful in production but the clearest possible introduction to passes and swaps.
05Prove the table wrong
Big O is theory, and the race is the check. Open the Sorting Algorithm Race and feed every algorithm the same array. The measured comparisons and moves should line up with this table: Insertion Sort at the top on sorted data, the three O(n log n) sorts clustered on random data, and the O(n^2) sorts fading fast as the size slider climbs.
06Frequently asked questions
QIs there a sorting algorithm that wins on everything?
No. Stability, memory, worst case, and simplicity trade off against each other. Real libraries ship hybrids instead of a single winner: Introsort starts as Quick Sort and falls back to Heap Sort, and Timsort blends Merge Sort with Insertion Sort.
QWhy does Shell Sort have a strange complexity like O(n^1.25)?
Shell Sort is Insertion Sort run over shrinking gaps. The total work depends on the gap sequence, and good sequences land between linear and quadratic. O(n^1.25) is the accepted average for practical gap choices.
QShould I memorize this table?
Memorize the shape instead: three O(n log n) sorts, four O(n^2) simple sorts, one linear non-comparison sort. Then remember one distinguishing fact each: Merge is stable, Quick is fastest, Heap needs no memory, Radix is linear, and the rest are educational.
QWhat do interviewers actually ask about sorting?
The most common questions are: when is Merge Sort preferred, why can Quick Sort be O(n^2) and how to avoid it, what stability means, and how to sort when memory is severely limited. Practicing the animated versions of each algorithm is the fastest way to answer.
Open any algorithm
Every row in the table links to a full step-by-step visualizer.