Sorting Algorithms Compared: Merge, Quick, Heap, Counting & When to Use Each

You'll almost never write a sorting algorithm at work, yet sorting comes up in interviews all the time. Partly that's direct ("implement merge sort", "why is quicksort's worst case quadratic?"), but mostly it's indirect: partitioning powers quickselect and Sort Colors, merging powers Merge K Sorted Lists and counting inversions, heaps power top-K problems, and knowing what your language's sort() costs is part of every complexity answer.

This guide gives you working code for each important algorithm in at least two languages, a dry run where it helps, the properties that interviewers probe (stability, in-place, adaptivity, worst case), and what real libraries do. Let's start with the summary table, then justify each row.

Sorting Algorithms Comparison Table

* Bubble sort is O(n) best case only with the early-exit flag. k is the key range, d the number of digits, b the base. Adaptive means faster on input that's already partly sorted. Quicksort's O(log n) stack assumes you recurse into the smaller partition first; naively it can be O(n) in the worst case.

What Stability Means and Why It Matters

A sort is stable if elements with equal keys keep their original relative order. That sounds academic until you sort records by more than one field.

Say you have orders already sorted by time, and you now sort them by city. With a stable sort, orders within each city stay in time order. With an unstable sort, they're scrambled:

This "sort by secondary key, then stable-sort by primary key" trick is exactly how radix sort works, and it's why spreadsheet column sorts and most UI table sorts rely on stable algorithms. Any unstable sort can be made stable by adding the original index as a tie-breaker, at the cost of extra memory.

Insertion Sort: The Small-Array Workhorse

Insertion sort builds a sorted prefix one element at a time, shifting larger elements right to make room. It's O(n²) in general but O(n + inversions), so it's very fast on small or nearly sorted arrays. That's why Timsort and introsort both switch to insertion sort for small subarrays, typically under a few dozen elements.

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:     # strict > keeps it stable
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key

static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

Bubble sort and selection sort exist mostly for teaching. Selection sort does the minimum number of swaps (n − 1), which matters only when writes are very expensive. Neither is used by real libraries.

Merge Sort: Guaranteed O(n log n) and Stable

Split the array in half, sort each half recursively, merge the two sorted halves. The recurrence T(n) = 2T(n/2) + O(n) gives O(n log n) in every case: log n levels, O(n) merge work per level.

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    return merge(merge_sort(a[:mid]), merge_sort(a[mid:]))

def merge(left, right):
    out = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:      # <= takes from the left on ties: stable
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    out.extend(left[i:])
    out.extend(right[j:])
    return out

static void mergeSort(int[] a) {
    mergeSort(a, new int[a.length], 0, a.length);
}

// sorts a[lo, hi)
static void mergeSort(int[] a, int[] tmp, int lo, int hi) {
    if (hi - lo < 2) return;
    int mid = (lo + hi) >>> 1;
    mergeSort(a, tmp, lo, mid);
    mergeSort(a, tmp, mid, hi);
    int i = lo, j = mid, k = lo;
    while (i < mid && j < hi) tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    while (i < mid) tmp[k++] = a[i++];
    while (j < hi) tmp[k++] = a[j++];
    System.arraycopy(tmp, lo, a, lo, hi - lo);
}

The Python version is clearest for explaining, but its slices allocate new lists at every level (still O(n log n) time, more memory traffic). The Java version allocates one buffer up front, which is what you'd mention as the production-quality approach. (lo + hi) >>> 1 avoids the integer overflow that (lo + hi) / 2 can hit on huge arrays.

Dry run on [5, 2, 4, 7, 1, 3, 2, 6]:

Where merge sort wins:

• Linked lists (Sort List, LeetCode 148): merging only relinks nodes, so no buffer is needed, and splitting uses slow/fast pointers.
• External sorting: data bigger than RAM is sorted in chunks, then the chunks are k-way merged with a heap. This is how databases sort large result sets.
• Counting inversions: during the merge, when you take from the right half, every remaining element in the left half forms an inversion with it. Add mid − i and you count inversions in O(n log n).
• Guaranteed worst case and stability, when both are required.

Quick Sort: Partitioning, Pivots and the Worst Case

Pick a pivot, partition the array so smaller elements go left and larger go right, then recurse on both sides. No merge step is needed because partitioning already puts the pivot in its final position.

Lomuto partition with a random pivot

#include <random>
#include <vector>
#include <utility>
using namespace std;

mt19937 rng(random_device{}());

int partition(vector<int>& a, int lo, int hi) {          // inclusive bounds
    int p = uniform_int_distribution<int>(lo, hi)(rng);
    swap(a[p], a[hi]);                                    // pivot to the end
    int pivot = a[hi], i = lo;                            // a[lo..i-1] < pivot
    for (int j = lo; j < hi; ++j)
        if (a[j] < pivot) swap(a[i++], a[j]);
    swap(a[i], a[hi]);                                    // pivot to final spot
    return i;
}

void quickSort(vector<int>& a, int lo, int hi) {
    while (lo < hi) {
        int p = partition(a, lo, hi);
        if (p - lo < hi - p) {            // recurse on the smaller side,
            quickSort(a, lo, p - 1);      // loop on the larger one:
            lo = p + 1;                   // stack depth stays O(log n)
        } else {
            quickSort(a, p + 1, hi);
            hi = p - 1;
        }
    }
}

Lomuto dry run on [3, 6, 1, 8, 2, 5] with pivot 5 (already last): j=0, 3 < 5, swap into slot 0. j=1, 6 stays. j=2, 1 < 5, swap into slot 1 giving [3,1,6,8,2,5]. j=3, 8 stays. j=4, 2 < 5, swap into slot 2 giving [3,1,2,8,6,5]. Finally swap the pivot into slot 3: [3,1,2,5,6,8]. Everything left of index 3 is smaller, everything right is larger.

Why the worst case is O(n²), and how libraries avoid it

If the pivot is always the smallest or largest element (for example, choosing the last element of an already sorted array), each partition peels off just one element: T(n) = T(n−1) + n = O(n²), with O(n) recursion depth. The fixes:

• Random pivot: expected O(n log n) on every input; the bad case needs consistently bad luck.
• Median-of-three (first, middle, last): handles sorted and reverse-sorted input well.
• Introsort: track recursion depth, and if it exceeds about 2·log n, switch to heap sort. Guarantees O(n log n) worst case. This is what C++ std::sort implementations do.
• Three-way partitioning: handles many duplicate keys, where plain Lomuto degrades to O(n²) on an all-equal array.

import random

def quicksort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo >= hi:
        return
    pivot = a[random.randint(lo, hi)]
    lt, i, gt = lo, lo, hi          # a[lo:lt] < p, a[lt:i] == p, a[gt+1:] > p
    while i <= gt:
        if a[i] < pivot:
            a[lt], a[i] = a[i], a[lt]
            lt += 1
            i += 1
        elif a[i] > pivot:
            a[i], a[gt] = a[gt], a[i]
            gt -= 1
        else:
            i += 1
    quicksort(a, lo, lt - 1)        # equal keys are never touched again
    quicksort(a, gt + 1, hi)

Partitioning is also the engine of quickselect: partition once, then recurse only into the side containing the k-th position. That's O(n) average for finding the k-th smallest element, covered in Kth Largest Element in an Array. The three-way partition is the same algorithm as Sort Colors in the two pointers guide.

Heap Sort: O(n log n) Worst Case in O(1) Space

Turn the array into a max-heap in place, then repeatedly swap the root (the maximum) with the last unsorted element and restore the heap on the shrunk prefix.

static void heapSort(int[] a) {
    int n = a.length;
    for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, i, n);   // O(n) build
    for (int end = n - 1; end > 0; end--) {
        swap(a, 0, end);            // max goes to its final position
        siftDown(a, 0, end);        // heap is now a[0, end)
    }
}

static void siftDown(int[] a, int i, int n) {
    while (true) {
        int l = 2 * i + 1, r = l + 1, big = i;
        if (l < n && a[l] > a[big]) big = l;
        if (r < n && a[r] > a[big]) big = r;
        if (big == i) return;
        swap(a, i, big);
        i = big;
    }
}

static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }

def heap_sort(a):
    n = len(a)

    def sift_down(i, size):
        while True:
            l, r, big = 2 * i + 1, 2 * i + 2, i
            if l < size and a[l] > a[big]:
                big = l
            if r < size and a[r] > a[big]:
                big = r
            if big == i:
                return
            a[i], a[big] = a[big], a[i]
            i = big

    for i in range(n // 2 - 1, -1, -1):
        sift_down(i, n)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]
        sift_down(0, end)

Building the heap bottom-up is O(n), not O(n log n), because most nodes are near the bottom and sift only a short distance. The extraction phase is n × O(log n). Heap sort is unstable because the root swap jumps elements across long distances, and it's slower in practice than quicksort because sift-down accesses memory in a scattered pattern (index i, then 2i+1) that's unfriendly to CPU caches. Its niche is as introsort's fallback. In interviews, heaps matter far more as priority queues than as a sort; see heap and priority queue problems.

Counting Sort and Radix Sort: Beating n log n

Counting sort

When keys are integers in a small range [0, k], count occurrences, turn counts into positions with a prefix sum, and place each element directly. O(n + k) time and space.

def counting_sort(a, max_val):
    count = [0] * (max_val + 1)
    for x in a:
        count[x] += 1
    for v in range(1, max_val + 1):
        count[v] += count[v - 1]          # count[v] = number of elements <= v
    out = [0] * len(a)
    for x in reversed(a):                 # reverse pass keeps equal keys in order
        count[x] -= 1
        out[count[x]] = x
    return out

vector<int> countingSort(const vector<int>& a, int maxVal) {
    vector<int> count(maxVal + 1, 0), out(a.size());
    for (int x : a) count[x]++;
    for (int v = 1; v <= maxVal; ++v) count[v] += count[v - 1];
    for (int i = (int)a.size() - 1; i >= 0; --i) out[--count[a[i]]] = a[i];
    return out;
}

For plain integers, the simpler "write each value count[v] times" version works. The prefix-sum version matters when you're sorting records by an integer key and need stability, which is exactly what radix sort needs. Use counting sort when k is O(n); sorting 10 numbers in the range 0 to 10⁹ this way would allocate a billion counters.

Radix sort (LSD)

Sort by the least significant digit, then the next, and so on, using a stable sort at each step. Because each pass is stable, ties on the current digit keep the order from earlier passes.

def radix_sort(a):
    if not a:
        return a
    exp, biggest = 1, max(a)
    while biggest // exp > 0:
        buckets = [[] for _ in range(10)]
        for x in a:
            buckets[(x // exp) % 10].append(x)   # appending keeps it stable
        a = [x for b in buckets for x in b]
        exp *= 10
    return a

Example on [170, 45, 75, 90, 802, 24, 2, 66]: by ones digit → [170, 90, 802, 2, 24, 45, 75, 66]; by tens → [802, 2, 24, 45, 66, 170, 75, 90]; by hundreds → [2, 24, 45, 66, 75, 90, 170, 802]. Complexity is O(d·(n + b)) for d digits in base b. For 32-bit integers with base 256 that's 4 passes, which is linear in n. Negative numbers need an offset or a separate pass for the sign.

Bucket sort is the third non-comparison sort: scatter values into buckets by range, sort each bucket, concatenate. It's O(n) expected for uniformly distributed data. In interviews it appears as Top K Frequent Elements (bucket by frequency) and Maximum Gap (pigeonhole buckets).

Why Comparison Sorts Can't Beat O(n log n)

Any comparison sort can be modelled as a binary decision tree: each internal node is a comparison "is a[i] < a[j]?", and each leaf is one possible output ordering. To sort correctly, the tree needs a distinct leaf for each of the n! input orderings. A binary tree with n! leaves has height at least log₂(n!), and

log₂(n!) ≥ log₂((n/2)^n/2) = (n/2)·log₂(n/2) = Ω(n log n)

So some input forces at least that many comparisons. Merge sort and heap sort are therefore asymptotically optimal among comparison sorts. Counting and radix sort escape the bound because they index by key values instead of comparing pairs. Being able to sketch this argument is a solid answer to "can you sort faster than n log n?"

What Python, Java, C++ and Others Actually Use

Two practical consequences come up in interviews. First, sorting an Integer[] or List<Integer> in Java is stable and somewhat slower (boxed objects, TimSort) than sorting an int[]. Second, the JavaScript default sort compares as strings, so [10, 9, 1].sort() gives [1, 10, 9]. Always pass a comparator for numbers.

Which Sorting Algorithm to Use When

Sorting Interview Questions and How to Answer Them

Conceptual questions

• "Merge sort or quicksort?" Quicksort for in-memory arrays (cache-friendly, in place, fast average); merge sort when you need stability, guaranteed worst case, linked lists or external data.
• "How do you avoid quicksort's worst case?" Random or median-of-three pivot, three-way partitioning for duplicates, introsort's depth limit.
• "Is heap sort stable? Why not?" No; the root-to-end swap moves equal elements past each other.
• "What does your language's sort use?" Use the table above; knowing Java's primitive/object split is a nice signal.
• "Sort a million 32-bit integers with limited memory." In-place quicksort or heap sort; if they're bounded, counting sort. If they don't fit in memory, external merge sort.

Coding problems built on sorting

Custom comparators: the bug magnet

public String largestNumber(int[] nums) {
    String[] s = new String[nums.length];
    for (int i = 0; i < nums.length; i++) s[i] = String.valueOf(nums[i]);
    Arrays.sort(s, (a, b) -> (b + a).compareTo(a + b));   // descending by concat
    if (s[0].equals("0")) return "0";                     // all zeros
    return String.join("", s);
}

from functools import cmp_to_key

def largestNumber(nums):
    s = list(map(str, nums))
    s.sort(key=cmp_to_key(lambda a, b: (a + b < b + a) - (a + b > b + a)))
    return "0" if s[0] == "0" else "".join(s)

If you can write merge sort, randomised quicksort and heap sort from memory, explain the stability column, and state what your language's built-in sort does, you've covered what interviewers ask about sorting directly. Everything else is applying these ideas inside other problems, and the complexity analysis guide covers how to cost those applications correctly.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.