Insertion Sort vs Selection Sort vs Bubble Sort: What Differs

Insertion sort vs selection sort vs bubble sort in one line: all three are O(n²) in the worst case, but they spend that budget differently. Insertion sort does only as many comparisons and shifts as the input is out of order, so it is O(n) on nearly sorted data and stable. Selection sort always makes exactly n(n-1)/2 comparisons, never fewer, but at most n - 1 swaps, the fewest writes of the three, and it is not stable. Bubble sort compares as much as selection sort on random input and swaps far more, is stable, and only its early-exit flag saves it on sorted input. For anything real, insertion sort is the one to reach for.

Algorithm	Comparisons: best / worst	Writes, stable?
Insertion	n - 1 / n(n-1)/2	one per inversion; stable
Selection	n(n-1)/2 / n(n-1)/2	at most n - 1 swaps; not stable
Bubble	n - 1 / n(n-1)/2	one swap per inversion; stable

The problem it solves

Big-O lumps the three together, and an interviewer who asks "which quadratic sort would you use, and why?" is testing whether you can see past the exponent. The honest answer counts two things separately: how many comparisons an algorithm makes, and how many times it writes into the array. Those two numbers, measured on the same inputs, separate the three cleanly and explain why one of them survives inside production sorts and the other two do not.

The intuition

All three keep a sorted region and grow it by one element per outer pass. They differ in what the inner loop does.

• Insertion sort picks up the next element and slides it left. Each comparison asks "is the element to my left bigger?"; each shift moves one bigger element one slot right. A shift fixes exactly one inversion, a pair that is in the wrong order, so the total work is n plus the number of inversions. Sorted input has zero inversions: n - 1 comparisons, no writes. Reversed input has every pair inverted: the full n(n-1)/2. The sort adapts to the input, and because an element never passes an equal one, it is stable.
• Selection sort scans the whole unsorted region for the minimum, then swaps it into place. The scan does not care how sorted the data already is; pass i always compares n - 1 - i times, so the total is n(n-1)/2 on every input, including sorted input. What it saves is writes: one swap per pass at most, n - 1 in all, and zero on sorted input. The long-distance swap is also what breaks stability: the minimum jumps over equal elements that were ahead of it.
• Bubble sort compares neighbours and swaps them when they are out of order. Like insertion sort, each swap fixes one inversion, so the swap count is the inversion count; but a swap is two writes where a shift is one, and bubble sort compares every adjacent pair on every pass, whether or not anything moves, until a pass with no swap ends it. On random data it makes about as many comparisons as selection sort and roughly twice the writes of insertion sort. The early exit gives it n - 1 comparisons on sorted input; a few out-of-place elements cost it many passes.

So: insertion sort wins on comparisons whenever the data is partly ordered and ties on random data; selection sort wins on writes, and only on writes; bubble sort wins nothing except the picture of large values floating to the end. That is why insertion sort is the finishing step inside library sorts for short runs, as which sorting algorithm to use explains, and why selection sort is the answer only when a write is far more expensive than a read, such as flash memory with limited write cycles.

Watch it run

The animation sorts [4, 1, 5, 2, 6, 3] with insertion sort. The first value is a sorted region of one. It picks up 1 and leaves a gap; 4 is bigger, so 4 slides right and 1 drops in. Picking up 5 takes no shifts, because 4 is not bigger. The 2 pushes 5 and 4 one slot right. The 6 drops straight in. The last key, 3, passes 6, 5 and 4. The closing frame counts six shifts in total, one per inversion. Selection sort on the same array would make fifteen comparisons no matter what, and bubble sort would make six swaps, twelve writes, across several passes.

The code

The lesson's insertion_sort, with the other two beside it, each taking a counter that records comparisons and writes. The same four inputs of 200 elements go through all three, and every result is checked against sorted():

import random

class Counter:
    """Counts comparisons between keys and writes into the list."""
    def __init__(self):
        self.comparisons = self.writes = 0
    def less(self, a, b):
        self.comparisons += 1
        return a < b

def insertion_sort(nums, c):
    for i in range(1, len(nums)):
        key, j = nums[i], i - 1
        while j >= 0 and c.less(key, nums[j]):   # slide bigger values one slot right
            nums[j + 1] = nums[j]; c.writes += 1
            j -= 1
        if j + 1 != i:
            nums[j + 1] = key; c.writes += 1      # drop the key into the gap
    return nums

def selection_sort(nums, c):
    n = len(nums)
    for i in range(n - 1):
        smallest = i
        for j in range(i + 1, n):                 # always scans the whole remainder
            if c.less(nums[j], nums[smallest]):
                smallest = j
        if smallest != i:
            nums[i], nums[smallest] = nums[smallest], nums[i]; c.writes += 2
    return nums

def bubble_sort(nums, c):
    n = len(nums)
    for end in range(n - 1, 0, -1):
        swapped = False
        for j in range(end):
            if c.less(nums[j + 1], nums[j]):
                nums[j], nums[j + 1] = nums[j + 1], nums[j]; c.writes += 2
                swapped = True
        if not swapped:                           # a clean pass: already sorted
            break
    return nums

random.seed(7)
n = 200
base = list(range(n))
nearly = base[:]                                  # sorted, then 5 random swaps
for _ in range(5):
    a, b = random.randrange(n), random.randrange(n)
    nearly[a], nearly[b] = nearly[b], nearly[a]
inputs = {"random": random.sample(range(1000), n), "nearly sorted": nearly,
          "reversed": base[::-1], "sorted": base[:]}

print(f"{'input':14}{'algorithm':11}{'compares':>9}{'writes':>8}")
for label, data in inputs.items():
    for name, sort in [("insertion", insertion_sort), ("selection", selection_sort), ("bubble", bubble_sort)]:
        c = Counter()
        assert sort(data[:], c) == sorted(data)
        print(f"{label:14}{name:11}{c.comparisons:9}{c.writes:8}")
print("n(n-1)/2 =", n * (n - 1) // 2)
# input         algorithm   compares  writes
# random        insertion       9685    9685
# random        selection      19900     384
# random        bubble         19872   18980
# nearly sorted insertion        756     703
# nearly sorted selection      19900      10
# nearly sorted bubble         16245    1114
# reversed      insertion      19900   20099
# reversed      selection      19900     200
# reversed      bubble         19900   39800
# sorted        insertion        199       0
# sorted        selection      19900       0
# sorted        bubble           199       0
# n(n-1)/2 = 19900

Read it row by row. On random input, insertion sort compares about half as often as the other two, 9,685 against 19,900 and 19,872, because it stops each inner loop as soon as it finds a smaller element; its writes equal its comparisons, roughly one shift per inversion. Selection sort's 19,900 is n(n-1)/2 exactly, on every row, while its 384 writes are the smallest number in the column. Bubble sort swaps 9,490 times, two writes each, for 18,980. Five random swaps in a sorted array cost insertion sort 756 comparisons, not far from the 199 of the sorted case; bubble sort's early exit does not fire until the stragglers have travelled, so it still pays 16,245. Reversed input is the worst case for all three and the one place bubble sort's two-writes-per-swap shows: 39,800 writes against insertion sort's 20,099.

Stability, on five elements whose keys tie. The tags record input order, and a stable sort keeps a before c and b before d:

class Tagged:
    """Compares by key only, so equal keys are truly equal; the tag shows input order."""
    def __init__(self, key, tag):
        self.key, self.tag = key, tag
    def __lt__(self, other):
        return self.key < other.key
    def __repr__(self):
        return f"{self.key}{self.tag}"

pairs = [Tagged(2, "a"), Tagged(1, "b"), Tagged(2, "c"), Tagged(1, "d"), Tagged(0, "e")]
for name, sort in [("insertion", insertion_sort), ("selection", selection_sort), ("bubble", bubble_sort)]:
    out = sort(pairs[:], Counter())
    stable = [p.tag for p in out] == [p.tag for p in sorted(pairs, key=lambda p: p.key)]
    print(f"{name:10} {out}  stable: {stable}")
# insertion  [0e, 1b, 1d, 2a, 2c]  stable: True
# selection  [0e, 1b, 1d, 2c, 2a]  stable: False
# bubble     [0e, 1b, 1d, 2a, 2c]  stable: True

Selection sort's first pass swapped the minimum, 0e, with 2a at the front, carrying 2a past 2c. Insertion and bubble sort only ever move an element past a strictly larger one, so equal keys keep their order.

The complexity

• Insertion sort: comparisons and shifts are n - 1 + inversions. Best O(n), average and worst O(n²), O(1) extra space, stable. The constant is small and the inner loop is a tight, cache-friendly sweep, which is why library sorts use it on runs of a few dozen elements.
• Selection sort: comparisons are always n(n-1)/2, so best, average and worst are all O(n²); swaps are at most n - 1, O(n) writes. O(1) extra space, not stable in the swap-based form.
• Bubble sort: best O(n) with the early-exit flag, average and worst O(n²) with about twice insertion sort's writes, O(1) extra space, stable.

Where it goes wrong

• Choosing by Big-O alone. All three say O(n²); the comparison and write counts above are what differ, and they differ by factors of two to a hundred on realistic inputs.
• Assuming selection sort is adaptive. It never is: 19,900 comparisons on a sorted array of 200. Only its write count benefits from order.
• Bubble sort without the flag. Drop swapped and sorted input costs n(n-1)/2 comparisons like everything else.
• Breaking insertion sort's stability. Writing nums[j] >= key in the shift condition moves equal elements past each other.
• Using any of them on large unsorted input. Past a few thousand elements the quadratic term dominates and merge sort or quick sort wins by orders of magnitude.

When it shows up in interviews

Directly, as "compare these three", and indirectly when an interviewer asks why a library's sort switches to insertion sort for small slices, or which sort to use when writes are expensive. A strong answer counts comparisons and writes separately, names inversions as the quantity insertion sort adapts to, and knows which two are stable. The per-algorithm details are in insertion sort explained, selection sort explained and bubble sort explained visually; the step-by-step shifts are in the insertion sort lesson.

How to say it in an interview

"All three are quadratic in the worst case, but they do different work. Insertion sort's cost is n plus the number of inversions, so it is linear on nearly sorted data, stable, and the one real sorts use on small runs. Selection sort always makes n(n-1)/2 comparisons, even on sorted input, but at most n - 1 swaps, so it is only worth it when writes are much more expensive than reads, and it is not stable. Bubble sort compares as much as selection sort on random data and writes about twice as much as insertion sort; the early-exit flag makes sorted input linear, but that is its only advantage. In practice: insertion sort, unless writes are the bottleneck."

Frequently asked questions

Which is better, insertion sort or selection sort?

Insertion sort, almost always. It makes fewer comparisons on any partly ordered input, runs in linear time on nearly sorted data and is stable. Selection sort makes n(n-1)/2 comparisons regardless of order; its only advantage is at most n - 1 swaps, which matters when writes are expensive.

Is bubble sort faster than insertion sort?

No. On random input bubble sort makes about twice as many comparisons and about twice as many writes, because every pass compares every adjacent pair and each swap is two writes. Both are linear on sorted input, but insertion sort stays near linear on nearly sorted input while bubble sort needs many passes.

Which sorting algorithms are stable: insertion, selection or bubble?

Insertion sort and bubble sort are stable: each moves an element only past strictly larger neighbours, so equal keys keep their input order. Selection sort is not stable in its usual form, because swapping the minimum into place carries the element it replaced past equal elements further along.