What is the fastest sorting algorithm?
QuickSort averages O(n log n) with exceptional cache efficiency, making it 2–3× faster than MergeSort on in-memory arrays. For integers in a bounded range, Counting Sort or Radix Sort run in O(n) — theoretically faster than any comparison sort. For nearly-sorted real-world data, TimSort wins. There is no single "fastest" — there is only the fastest for your data.
Sorting Algorithm Complexity Cheatsheet
Every algorithm's time and space complexity at a glance. Bookmark this. It's what you'll reach for before every interview and every code review.
| Algorithm | Best Case | Average Case | Worst Case | Space | Stable? | Method |
|---|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | ✔ Stable | Exchange |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | ✗ Unstable | Selection |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | ✔ Stable | Insertion |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | ✔ Stable | Merge D&C |
| Quick Sort | O(n log n) | O(n log n) | O(n²)* | O(log n) | ✗ Unstable | Partition D&C |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | ✗ Unstable | Selection |
| Shell Sort | O(n log n) | O(n log²n) | O(n log²n) | O(1) | ✗ Unstable | Insertion |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | ✔ Stable | Non-comparison |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n+k) | ✔ Stable | Non-comparison |
| Tim Sort | O(n) | O(n log n) | O(n log n) | O(n) | ✔ Stable | Hybrid |
* QuickSort worst-case O(n²) is rare in practice and avoided with randomised pivot. k = range of input values. n = number of elements.
QuickSort vs MergeSort — The Definitive Verdict
This is the single most-asked sorting algorithm interview question. Here is the honest, nuanced answer — not the generic textbook version.
The Deeper Story: Cache Lines and Why Theory Lies
Both QuickSort and MergeSort have O(n log n) average complexity — identical on paper. But constants matter, and those constants are dominated by how your CPU handles memory. QuickSort pivots around a single element and swaps nearby elements, so all accesses stay in L1/L2 cache (64–256KB). MergeSort allocates a fresh O(n) array at every merge step, causing cache misses. On a modern CPU sorting 1M integers, QuickSort finishes in ~80ms; MergeSort takes ~200ms — same Big-O, 2.5× real difference.
C++'s std::sort uses IntroSort — a hybrid that starts as QuickSort, switches to HeapSort if recursion depth exceeds 2·log(n) (to avoid O(n²) worst case), and falls back to InsertionSort for small arrays. Java's Arrays.sort() for primitives uses Dual-Pivot QuickSort (Yaroslavskiy, 2009); for objects it uses TimSort to preserve stability.
What does stable mean — and why does it matter?
A sorting algorithm is stable if it preserves the original relative order of elements that compare as equal. This sounds abstract — here's why it's crucial in practice.
A Concrete Example: Sorting a Student Roster
Imagine you have a list of students, each with a name and grade. You want to sort first by grade, then by name within each grade.
Bob — B
Carol — A
Dave — B
Eve — A
Carol — A
Eve — A
Bob — B
Dave — B
With a stable sort, Alice, Carol, and Eve maintain their alphabetical order within grade A — the sub-sort is preserved for free. An unstable sort may output Eve, Alice, Carol in any order.
Insertion Sort
Merge Sort
Tim Sort
Counting Sort
Radix Sort
Heap Sort
Selection Sort
Shell Sort
IntroSort (C++)
Stability matters when you sort by multiple criteria sequentially, sort objects where equality is partial, or guarantee deterministic output for user-facing features (like sort-by-date that preserves name order). Python's built-in sorted() is stable by design — it was a deliberate choice that enables the Schwartzian transform idiom.
All 10 Algorithms — Fully Explained
Click any algorithm to expand the full technical breakdown: how it works, pseudocode, when to use it, and what to avoid.
Repeatedly steps through the array, compares adjacent pairs, and swaps them if out of order. After each full pass, the largest unsorted element "bubbles" to its correct position at the end. The optimised version stops early if no swaps occurred in a pass — achieving O(n) on already-sorted input.
- Learning and teaching algorithm fundamentals
- Detecting if an array is already sorted (O(n) best case)
- Arrays so small that code simplicity > performance
- Any production sorting of non-trivial data sizes
- N > ~100 elements
Maintains a sorted sub-array from the left. For each new element, "inserts" it into the correct position by shifting larger sorted elements right. Like sorting playing cards in your hand — you pick each card and slide it into position.
Key insight: InsertionSort is the algorithm of choice for small arrays (n ≤ 32). Both TimSort and IntroSort use InsertionSort internally for subarrays below a threshold because its low overhead beats O(n log n) algorithms at small scales.
- Nearly-sorted data (O(n·k) where k = max displacement)
- Online sorting — elements arriving one at a time
- Small arrays or as subroutine in hybrid sorts
Divides the array into sorted and unsorted portions. On each pass, scans the unsorted portion to find the minimum element, then swaps it into the correct position. Exactly n−1 swaps total, regardless of input.
Why it matters despite O(n²): In environments where writes are very expensive (e.g. EEPROM, flash memory with limited write cycles), Selection Sort's guaranteed O(n) swaps makes it the right choice even though comparisons are still O(n²).
- Minimising write operations (flash memory, EEPROM)
- When write cost >> read cost
- Teaching selection-based algorithm design
Classic divide-and-conquer: recursively split the array in half until each subarray has one element (trivially sorted), then merge pairs of sorted subarrays into a single sorted array. Invented by John von Neumann in 1945.
External sorting: MergeSort is the algorithm of choice for sorting data that doesn't fit in memory (database records, log files). You can merge sorted chunks from disk without loading everything into RAM.
- When stability is non-negotiable
- External sorting (data larger than RAM)
- Sorting linked lists (no random access needed)
- Guaranteed O(n log n) — no worst-case surprise
Selects a pivot element and partitions the array so all smaller elements move left and all larger elements move right. Recursively applies to both partitions. Invented by Tony Hoare in 1959–1961. The fastest in-memory comparison sort for random data.
Pivot strategies: (1) Last element — simple but O(n²) on sorted input. (2) Random pivot — avoids adversarial inputs. (3) Median-of-three — best practical heuristic. (4) Dual-pivot — Java's approach, reduces average comparisons by ~5%.
- General-purpose in-memory sorting
- Arrays that fit in CPU cache
- When average-case speed matters most
- Random or uniformly distributed data
Uses a max-heap data structure. Phase 1: Build a max-heap in O(n) time — rearrange the array so every parent is larger than its children. Phase 2: Repeatedly extract the maximum (root), swap it to the end, then re-heapify the reduced heap. Gives O(n log n) guaranteed with O(1) extra space.
The catch: Poor cache locality (accesses jump around the array non-sequentially) makes it slower than QuickSort by a constant factor, despite identical Big-O. Used mainly when O(1) space and O(n log n) worst-case are both required.
- Memory-constrained environments (O(1) space)
- Real-time systems needing worst-case guarantees
- Part of IntroSort (fallback when QS recurses too deep)
A generalisation of Insertion Sort. Instead of comparing adjacent elements, Shell Sort compares elements separated by a "gap" that shrinks each pass. Large gaps allow elements to move long distances quickly; by the final pass (gap=1), the array is nearly sorted so InsertionSort completes in near-linear time. Performance depends heavily on gap sequence choice — Ciura's gap sequence (1, 4, 10, 23, 57, 132, 301, 701…) gives the best known results empirically.
- Embedded systems or environments where recursion is prohibited
- Medium datasets where O(n log n) sorts aren't available
- When O(1) space and reasonable speed are both needed
Breaks the O(n log n) comparison-sort lower bound by not comparing elements at all. Counts occurrences of each value in a frequency table of size k (range of input), then reconstructs the sorted array by iterating the count table. O(n+k) time and space, where k = max value − min value.
The critical constraint: Only works for non-negative integers (or values mappable to integers) in a known, bounded range. If k >> n (e.g. sorting 100 values in range 0–1,000,000), the O(k) space and time overhead makes it impractical. It shines when k is small relative to n — sorting grades (0–100), ages (0–120), ASCII characters (0–127), etc.
- Grades, ages, character frequencies, small-range integers
- As subroutine in Radix Sort
- When n and k are both reasonable in size
Sorts integers digit-by-digit, from least significant digit (LSD) to most significant (MSD), using Counting Sort as a stable subroutine at each digit position. After d passes (where d = number of digits), the array is fully sorted. O(d·n) total — effectively O(n) for fixed-width integers.
Real-world applications: Sorting IP addresses, phone numbers, fixed-length codes (ZIP codes, credit card numbers), and is used in database index sorting. In GPU-accelerated computing, Radix Sort outperforms QuickSort because its memory access pattern is more parallelisable.
▶ Watch Radix Sort →Designed by Tim Peters for Python 2.3 (2002), TimSort is the most practically important sorting algorithm today — it's the default in Python (list.sort(), sorted()), Java (Arrays.sort(Object[])), Kotlin, Swift, and Android.
It detects naturally occurring runs (already-sorted sequences) in the data. Short runs are extended to minimum size (RUN ≈ 32–64) using InsertionSort. These runs are then merged using a MergeSort variant with sophisticated merge-order optimisation (the galloping mode). On real-world data that contains partial ordering, TimSort can approach O(n) speed.
- Real-world data is rarely fully random — partial order is common
- Database records, log files, user events often arrive partially sorted
- TimSort exploits this, MergeSort and QuickSort ignore it
- Stable, correct, and fast in all cases — the complete package
Which sorting algorithm should you use?
Stop memorising everything — learn the decision tree. Every real-world choice comes down to these questions.
sorted(), Java's Arrays.sort(), JavaScript's Array.prototype.sort() — these are all tuned, production-hardened hybrids. You need to choose yourself only when (a) you have very specific data characteristics, (b) you have unique constraints (memory, stability, data type), or (c) you're answering an interview question.The 8 sorting algorithm interview questions you will face
These are the questions hiring managers at FAANG-tier companies actually ask. Not exhaustive — targeted. Know these cold.
sorted(people, key=lambda x: (x.last, x.first)) — single-pass with tuple key.Sorting algorithms in the real world
Theory is one thing. Here's what the systems you use every day actually run under the hood.
list.sort() and sorted() use it. Designed by Tim Peters, CPython dev, in 2002.std::sort uses IntroSort: starts as QuickSort, falls to HeapSort if depth > 2·log(n), uses InsertionSort for small partitions. Best of all worlds.Array.prototype.sort() was unstable until V8 7.0 (Chrome 70). Now uses TimSort — the spec mandates stability since ECMAScript 2019.