Which Sorting Algorithm to Use: Four Questions That Decide

Every sorting algorithm you learn comes with a Big-O line, and it is tempting to rank them by it and always reach for the winner. That misses the point. The fastest sort for forty nearly ordered photos is not the fastest for a million pixel values, and neither is the right one if equal items must keep their order. Choosing a sort is a short decision procedure about your data, and interviewers ask about it precisely because it shows whether you understand why the algorithms differ.

The problem it solves

"Which sort would you use?" hides several real constraints:

• Size. For small inputs, constant factors and setup cost matter more than growth rate.
• Existing order. Data that arrives almost sorted, such as timestamps or an appended-to list, is far cheaper for an adaptive sort.
• Value range. If keys are small integers, you can avoid comparisons altogether.
• Stability. When records tie on the sort key, a stable sort keeps their original relative order. Sorting by date and then expecting same-second photos to stay in capture order depends on it.
• Memory. Some sorts need a second array; others work in place.

The intuition

The lesson reduces it to four questions, asked in order, with the first "yes" deciding:

1. Is n tiny (around 32 or fewer), or is the input nearly sorted? Use insertion sort. Its inner loop shifts an element left only past elements that are larger, so its work is O(n + inversions), where an inversion is a pair that is out of order. Nearly sorted input has few inversions, so it runs close to linear, and it has almost no overhead.
2. Do the values fit a small integer range? Use counting sort: tally how many times each value occurs and write them back out, O(n + k) for k possible values, with no comparisons at all. It is the reason sorting a billion bytes is easy.
3. Is stability required? Use merge sort: stable and guaranteed O(n log n), at the cost of O(n) extra space.
4. Anything else: quick sort, in place, O(n log n) on average and usually fastest in practice, with an O(n²) worst case that good pivot choice makes very unlikely.

Two refinements are worth saying out loud. For a guaranteed O(n log n) in O(1) extra space without stability, heap sort fills the niche. And libraries rarely pick just one: as of September 2026, Python's built-in sorted is a stable, adaptive merge sort derived from Timsort that uses insertion sort on short runs, and C++'s std::sort is typically an introsort, a quick sort that falls back to heap sort when recursion gets too deep. The four questions are what those hybrids answer internally.

Watch it run

The animation traces four real workloads through the same four questions. There is no best sort, only a best sort for this data, and four questions get you there. New workload: 40 photos by date, n = 40 and nearly sorted. The first question answers yes: tiny and almost in order, insertion sort's shift loop barely runs, so it beats anything with setup cost. Next, 1M pixel values, with values 0 to 255. No, it is not tiny or nearly sorted, so drop down a question. Huge n, but only 256 distinct values: counting sort tallies them in O(n + k) without a single comparison. Then a 200k photo library where same-second captures must keep their order. No, no, and then stability decides it: merge sort, guaranteed O(n log n). Last, 500k log lines, no ties, memory tight. Nothing special about the data and no stability needed, so quick sort, which sorts in place and is fastest in practice. The same four questions every time: learn the questions, not a ranking of the algorithms.

The code

The lesson's decision function on the four workloads, then the four algorithms themselves, with insertion sort counting its shifts on nearly sorted versus shuffled input:

def choose_sort(n, nearly_sorted, small_int_range, needs_stable):
    if n <= 32 or nearly_sorted:
        return "insertion sort"       # tiny overhead wins
    if small_int_range:
        return "counting sort"        # O(n + k), no comparisons
    if needs_stable:
        return "merge sort"           # stable, guaranteed n log n
    return "quick sort"               # fast in place, average n log n

workloads = [(40, True, False, True),            # 40 photos by date
             (1_000_000, False, True, False),    # pixel values 0-255
             (200_000, False, False, True),      # photo library, ties keep order
             (500_000, False, False, False)]     # log lines, no ties
for w in workloads:
    print(choose_sort(*w))
# insertion sort
# counting sort
# merge sort
# quick sort

def insertion_sort(a, key=lambda x: x):
    a, shifts = list(a), 0
    for i in range(1, len(a)):
        x, j = a[i], i - 1
        while j >= 0 and key(a[j]) > key(x):      # strict: equal keys stay put
            a[j + 1] = a[j]
            j -= 1
            shifts += 1
        a[j + 1] = x
    return a, shifts

def merge_sort(a, key=lambda x: x):
    if len(a) <= 1:
        return list(a)
    mid = len(a) // 2
    left, right = merge_sort(a[:mid], key), merge_sort(a[mid:], key)
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if key(right[j]) < key(left[i]):          # take left on ties: stable
            out.append(right[j]); j += 1
        else:
            out.append(left[i]); i += 1
    return out + left[i:] + right[j:]

def quick_sort(a, key=lambda x: x):
    a = list(a)
    def part(lo, hi):
        if lo >= hi:
            return
        p, i = key(a[hi]), lo
        for j in range(lo, hi):
            if key(a[j]) < p:
                a[i], a[j] = a[j], a[i]; i += 1   # long-distance swaps break ties
        a[i], a[hi] = a[hi], a[i]
        part(lo, i - 1); part(i + 1, hi)
    part(0, len(a) - 1)
    return a

def counting_sort(a, k=256):
    counts = [0] * k
    for x in a:
        counts[x] += 1
    return [v for v in range(k) for _ in range(counts[v])]

import random
rng = random.Random(32)
nearly = list(range(1_000))
for _ in range(5):
    i = rng.randrange(999)
    nearly[i], nearly[i + 1] = nearly[i + 1], nearly[i]   # five local swaps
shuffled = rng.sample(range(1_000), 1_000)
print(insertion_sort(nearly)[1], insertion_sort(shuffled)[1])   # 5 241241

Five shifts against 241,241 on the same thousand numbers: that is question one. Now stability, on photos that tie on their timestamp:

photos = [("09:00:01", "IMG_1"), ("09:00:00", "IMG_2"),
          ("09:00:01", "IMG_3"), ("09:00:00", "IMG_4")]
by_key = lambda p: p[0]
print([name for _, name in merge_sort(photos, by_key)])
print([name for _, name in quick_sort(photos, by_key)])
# ['IMG_2', 'IMG_4', 'IMG_1', 'IMG_3']
# ['IMG_4', 'IMG_2', 'IMG_1', 'IMG_3']

Merge sort keeps IMG_2 before IMG_4, as they arrived; quick sort's swap carried IMG_4 past its twin. Checked on 2,000 seeded random inputs: every sort equals sorted(), insertion sort's shift count equals a brute-force count of every out-of-order pair, and the stable sorts match Python's stable sorted on records with many ties:

rng = random.Random(32)
ok, reordered = True, 0
for _ in range(2_000):
    n = rng.randint(0, 60)
    xs = [rng.randint(0, 255) for _ in range(n)]
    want = sorted(xs)
    got, shifts = insertion_sort(xs)
    ok &= got == merge_sort(xs) == quick_sort(xs) == counting_sort(xs) == want
    inversions = sum(xs[i] > xs[j] for i in range(n) for j in range(i + 1, n))
    ok &= shifts == inversions                    # brute force: count every pair
    recs = [(rng.randint(0, 5), i) for i in range(n)]   # few keys, many ties
    stable = sorted(recs, key=by_key)             # Python's sort is stable
    ok &= merge_sort(recs, by_key) == insertion_sort(recs, by_key)[0] == stable
    reordered += quick_sort(recs, by_key) != stable
print(ok, reordered)                              # True 1848

Quick sort reordered ties in 1,848 of the 2,000 record lists. It still sorted them; it just did not preserve arrival order.

The complexity

• Insertion sort: O(n + inversions), so O(n) nearly sorted and O(n²) in the worst case; O(1) extra space; stable.
• Counting sort: O(n + k) time and O(k) extra space; stable when written to carry records.
• Merge sort: O(n log n) always; O(n) extra space; stable.
• Quick sort: O(n log n) average, O(n²) worst; O(log n) stack on average; not stable.
• The Big-O cheat sheet keeps all of these, plus heap sort, on one page.

Where it goes wrong

• Ranking by Big-O alone. On 20 items, the "slow" quadratic sort often wins.
• Assuming stability. Sorting by a second key and expecting the first order to survive only works with a stable sort.
• Counting sort on a wide range. With 32-bit keys, k dwarfs n; that is where radix sort comes in.
• Naive pivots. A quick sort that always picks the last element degrades to O(n²) on already sorted input.
• Writing your own in production. The library sort is almost always right; the questions tell you which key and stability to ask for.

When it shows up in interviews

As "which sort would you use for...?" with a twist in the data, as "is this sort stable?", and as a follow-up after you implement merge sort or quick sort. Insertion sort comes up whenever the input is described as nearly sorted.

How to say it in an interview

"There's no single best sort, so I ask about the data. If it's tiny or nearly sorted, insertion sort, because its cost is n plus the number of inversions. If the keys are small integers, counting sort in O(n plus k) with no comparisons. If equal keys must keep their order, a stable O(n log n) sort like merge sort, paying O(n) space. Otherwise quick sort in place, average n log n, with randomised or median pivots to avoid the quadratic case. In practice I'd call the language's sort, which is already a hybrid of these, and just make sure its stability matches what I need."