Sorting Algorithms Cheat Sheet
Every sorting algorithm's complexity, stability, and sweet spot in one table. Click any algorithm to watch it run step by step.
The Table
| Algorithm | Best | Average | Worst | Space | Stable | Best For |
|---|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Teaching, and verifying an array is sorted in one O(n) pass |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No | When writes are expensive — makes at most n−1 swaps |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Small or nearly-sorted arrays; the base case inside real hybrid sorts |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | Guaranteed O(n log n), stable — linked lists, external sorting, multi-key sorts |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Fastest general-purpose in-memory sort in practice (with good pivots) |
How to Choose
- Default choice:your language's built-in sort — it is a tuned hybrid (Timsort, introsort) that already handles the edge cases.
- Need stability (multi-key sorts, sorting records): Merge Sort, or any stable built-in.
- Guaranteed worst case(real-time systems, adversarial input): Merge Sort's unconditional O(n log n).
- Nearly-sorted data: Insertion Sort approaches O(n) as the input approaches sorted order.
- Minimal writes (flash memory, huge records): Selection Sort makes at most n−1 swaps.
Head-to-Head Comparisons
Frequently Asked Questions
Which sorting algorithm is the fastest?
For general in-memory sorting, Quick Sort is usually fastest in practice thanks to cache-friendly in-place partitioning, despite its O(n²) worst case. Merge Sort guarantees O(n log n) in every case and is stable, at the cost of O(n) extra space. Real standard libraries ship hybrids: Python and Java use Timsort (merge/insertion), C++ uses introsort (quick/heap/insertion).
What does it mean for a sorting algorithm to be stable?
A stable sort preserves the relative order of elements that compare equal. Sorting people by department after sorting by name keeps each department alphabetized only if the second sort is stable. Bubble, Insertion, and Merge Sort are stable; Selection and Quick Sort are not (in their standard forms).
Which sorting algorithm should I learn first?
Start with Bubble Sort to understand comparisons and swaps, then Insertion and Selection Sort to see two different quadratic strategies, then Merge Sort for divide-and-conquer and Quick Sort for partitioning. Watching each run step by step makes the differences concrete far faster than re-reading pseudocode.
When is an O(n²) algorithm actually fine?
For small inputs (a few dozen elements), quadratic algorithms are often faster than O(n log n) ones because their constant factors are tiny — which is exactly why production hybrid sorts switch to Insertion Sort for small runs. They are also fine when simplicity matters more than speed, or when data is nearly sorted (Insertion Sort approaches O(n) there).