Comparison Sorts: Insertion, Bubble, Selection, Merge & Heapsort

Why a dedicated sorting topic, this late in the roadmap

You've been using sorted()/.sort() since Arrays & Hashing without a second thought, and that's the correct instinct for almost every interview — a built-in O(n log n) sort is never the wrong answer to reach for. This topic exists for the narrower, real skill interviewers occasionally probe for: knowing what's actually happening inside that call, being able to derive a sort from scratch when asked, and recognizing the handful of situations where the "obviously correct" O(n log n) bound isn't actually the best you can do. That last point matters more than it sounds — Sorting is also the topic that quietly underpins several others you've already covered (Heaps' quickselect, Intervals' sweep line, external merge sort behind every database's ORDER BY) and several still ahead (Divide & Conquer–flavored geometry problems).

The comparison-sort landscape

Algorithm	Time (avg)	Time (worst)	Space	Stable?	In-place?
Bubble sort	O(n²)	O(n²)	O(1)	Yes	Yes
Insertion sort	O(n²)	O(n²)	O(1)	Yes	Yes
Selection sort	O(n²)	O(n²)	O(1)	No	Yes
Merge sort	O(n log n)	O(n log n)	O(n)	Yes	No
Quicksort	O(n log n)	O(n²)	O(log n)	No	Yes
Heapsort	O(n log n)	O(n log n)	O(1)	No	Yes

"Stable" means equal elements keep their relative input order — this matters the moment you sort by one key while needing to preserve an earlier sort's order on ties (e.g., sort employees by department, but within each department keep them in hire-date order from a previous pass). It's a detail almost nobody asks about directly, but it's exactly the kind of thing that separates "I called .sort()" from "I understand what .sort() guarantees."

Insertion sort: the one that's secretly useful in production

Insertion sort builds the sorted output one element at a time, shifting each new element left past everything larger than it — the same motion as sorting a hand of playing cards as you pick them up. It's O(n²) in general, but it has a property no other simple sort has: it's O(n·k) where k is the maximum distance any element is from its sorted position, so on nearly sorted data (small k) it's close to linear.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

This is why production sort implementations aren't pure merge sort or quicksort at all — Python's list.sort() (Timsort) and Java's Arrays.sort() for objects both switch to insertion sort for small subarrays (typically n < 16–64) as the base case of their divide-and-conquer recursion, because insertion sort has lower constant-factor overhead than recursing all the way down to single elements, and it's the fastest simple sort on the small, often-nearly-sorted runs that show up in real data. Timsort specifically also detects already-sorted (or reverse-sorted) runs in the input and skips work entirely on them — this is the single biggest reason sorted() on real-world data is frequently faster than its O(n log n) worst-case bound would suggest.

Bubble sort: how to speed up something O(n²) without changing its complexity class

Bubble sort repeatedly swaps adjacent out-of-order elements, so the largest unsorted element "bubbles" to its correct position each pass. The textbook version is a good teaching tool for exactly one reason: it's the clearest example of the gap between "asymptotically optimal" and "the constant factors and early-exit conditions that make code actually fast on real inputs" — a skill an interviewer can probe for even without changing the underlying complexity class.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

Two-times speedup, no algorithmic change: the inner loop's upper bound n - 1 - i already avoids re-scanning the tail that's already bubbled into place — a naive version that always scans to n - 1 redoes work for no reason. If you started from that naive version, tightening the bound alone is close to a 2x constant-factor win on top of not changing anything about the algorithm's shape.

A much larger speedup (the "50x" version) with a real algorithmic change — cocktail shaker sort: bubble sort only ever moves the largest element into place each pass, so an array that's sorted except for one small value stuck near the end still takes O(n) passes to walk it all the way back. Cocktail shaker sort (bidirectional bubble sort) alternates direction each pass — bubble the largest to the right, then bubble the smallest to the left, then repeat — which fixes exactly this pathology:

def cocktail_shaker_sort(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        swapped = False
        for i in range(left, right):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
        right -= 1
        for i in range(right, left, -1):
            if arr[i - 1] > arr[i]:
                arr[i - 1], arr[i] = arr[i], arr[i - 1]
                swapped = True
        left += 1
        if not swapped:   # early exit: nothing moved, already sorted
            break

The early-exit swapped flag is the other lever: a single pass with zero swaps proves the array is already sorted, letting you terminate in O(n) instead of grinding through all O(n) remaining passes. Neither of these tricks changes bubble sort's O(n²) worst-case classification — an adversarial input (e.g., every small element clustered at the wrong end) still forces close to the full quadratic work. What changes is the practical constant factor and the best-case/average-case behavior, which is precisely the distinction an interviewer asking "how would you speed this up?" is listening for: naming the early-exit condition and the bidirectional-scan fix, rather than reaching for an unrelated O(n log n) algorithm, shows you understand why the naive version is slow, not just that it's slow.

Selection sort ↔ Heapsort: the same idea, two different "find the max" mechanisms

Selection sort repeatedly scans the unsorted remainder for its minimum (or maximum) and swaps it into place:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

This is O(n²) because "find the minimum of the remaining n−i elements" costs O(n−i) with a linear scan, repeated n times. Heapsort is selection sort with that linear scan replaced by a heap. If you've internalized the Heaps & Priority Queues topic, the connection is immediate: build a max-heap from the whole array in O(n) (Floyd's build-heap, covered there), then repeatedly extract the max (O(log n) instead of O(n−i)) and place it at the end of the unsorted region.

import heapq

def heap_sort(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        _sift_down_max(arr, i, n)
    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]   # move current max to its final position
        _sift_down_max(arr, 0, end)            # restore heap property on the shrunken heap

Swapping the O(n) linear "find max" for an O(log n) heap extraction is exactly what takes selection sort's O(n²) down to heapsort's O(n log n) — same outer structure ("repeatedly remove the extreme element and place it"), different data structure backing the removal. This is a genuinely useful thing to say out loud in an interview: it reframes two "separate" algorithms you memorized as one idea applied with two different tools, which reads as understanding rather than recall.

Merge sort: the canonical divide-and-conquer algorithm

Merge sort splits the array in half, recursively sorts each half, then merges the two sorted halves in O(n):

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return _merge(left, right)

def _merge(left, right):
    result, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

This is the textbook T(n) = 2T(n/2) + O(n) recurrence from Big-O & Complexity Analysis — two half-size recursive calls plus O(n) work to combine — giving O(n log n) guaranteed, not just expected. That worst-case guarantee, plus stability (equal elements never cross each other during a merge, since the <= comparison always prefers left on ties), is merge sort's whole selling point over quicksort.

The realistic, non-asymptotic optimization that matters in practice: the recursive version above allocates a brand-new list at every single call — that's real, measurable overhead that doesn't show up in the O(n log n) bound but absolutely shows up in wall-clock time. Production-grade merge sorts fix this two ways, both worth naming even if you don't implement them under interview time pressure: (1) allocate one auxiliary buffer up front and merge into alternating halves of it instead of allocating per call, and (2) switch to insertion sort below a small threshold size, for the same reason described above. Both are "constant factor" fixes — they don't change the O(n log n) classification, but they're the difference between a merge sort that's merely correct and one that's competitive with a well-tuned quicksort in practice.

Complexity analysis — the numbers to have memorized cold

Algorithm	Best	Average	Worst	Extra space	Why the worst case happens
Insertion sort	O(n) (nearly sorted)	O(n²)	O(n²)	O(1)	Reverse-sorted input: every element shifts all the way left
Bubble / cocktail shaker	O(n) (already sorted, with early exit)	O(n²)	O(n²)	O(1)	Reverse-sorted input, or one bad element far from its slot
Selection sort	O(n²)	O(n²)	O(n²)	O(1)	No early exit possible — always scans the full remainder
Merge sort	O(n log n)	O(n log n)	O(n log n)	O(n)	No worst case — recursion depth and merge cost are input-independent
Heapsort	O(n log n)	O(n log n)	O(n log n)	O(1)	Same — heap operations are always O(log n) regardless of input order

Pitfalls and interview gotchas

Confusing "stable" with "in-place." They're independent properties — quicksort is in-place but not stable; merge sort (as usually implemented) is stable but not in-place. Know both for every algorithm in the table above; interviewers ask this as a quick follow-up more often than they ask for a full derivation.
Claiming merge sort has O(1) space. The classic array-based implementation needs O(n) auxiliary space for the merge step — the recursion depth is O(log n), but the buffers are O(n). An in-place merge sort exists but has significantly worse constants and is rarely expected.
Forgetting why insertion sort is the right base case for hybrid sorts, and reflexively assuming "simple sorts are always strictly worse" — the nearly-sorted-data argument above is the exact reason they aren't.
Not naming the recurrence when asked to derive merge sort's complexity. "T(n) = 2T(n/2) + O(n), which solves to O(n log n) by the master theorem" is the answer a Senior-level interviewer wants to hear, not just the final bound.

How to talk about this in an interview

"For a general sort I'd reach for the language's built-in sort — it's O(n log n) and well-tuned. If asked to implement one from scratch, I'd pick merge sort for a guaranteed worst-case bound and stability, or quicksort for better average-case constants and O(log n) space if worst-case time isn't a hard requirement — and I'd mention that real sort implementations fall back to insertion sort on small subarrays, since that's faster in practice below a certain size regardless of which divide-and-conquer algorithm you're using."

Further Resources (Optional)

Practice Problems

Interview relevancy:!!!Critical — must-have!!Important — highly recommended!Good to have~Niche — rarely asked

H-IndexMedium!!2/520m
Sort an ArrayMedium!!3/535m
Largest NumberMedium!!3/525m

Optional Practice (Extra Reps)

For once you've cleared the main set above and want more reps on this pattern. These don't count toward the roadmap's progress stats — solve them purely for your own benefit.

Pancake SortingMedium~2/520m
Insertion Sort - Part 2HackerRank~1/515m