Insertion Sort Explained: Shifts, Inversions, Nearly Sorted Data

Insertion sort is how most people sort a hand of cards: pick up one card at a time and slide it left until it sits in the right place. It is O(n²) in the worst case, so it looks like something to learn and forget. It is not. It is the fastest simple sort on small or nearly sorted input, which is why production sorts still call it on short runs, and its cost has an exact meaning: the number of shifts equals the number of inversions in the input.

The problem it solves

Sort a list in place, using constant extra memory, keeping equal values in their original order, and doing very little work when the list is already almost sorted.

Bubble sort and selection sort also sort in place with O(1) memory, but they do not adapt the same way. Selection sort always makes about n²/2 comparisons, even on sorted input. Bubble sort with an early-exit flag finishes a sorted list in one pass, but one small value near the end still costs a full pass for every slot it has to travel. Plain merge sort does the same work on sorted input and needs O(n) extra space. Insertion sort does work proportional to how disordered the input actually is, and that property is the reason it survives.

The intuition

Split the list into two parts: a sorted region on the left, which starts as just the first element, and the unsorted rest. Repeat one move until the rest is empty:

1. Pick up the next element, the key, which leaves a gap where it was.
2. While the value just left of the gap is bigger than the key, slide that value one slot right. The gap moves one slot left.
3. When the value to the left is not bigger, or the gap reaches the front, drop the key into the gap.

After each round the sorted region is one element longer and still sorted.

The cost has a precise description. An inversion is a pair of positions where the earlier value is bigger than the later one. Every shift moves a bigger value past the key, which removes exactly one inversion and creates none. A sorted list has zero inversions. So the total number of shifts is exactly the number of inversions in the input, no more and no less.

That one fact explains every complexity claim. A sorted list has no inversions, so the algorithm does no shifts and one comparison per element: O(n). A reversed list has every pair inverted, n(n - 1)/2 of them: O(n²). A list with only a handful of elements out of place has a handful of inversions, and costs barely more than one pass. The Big-O cheat sheet lists the same best and worst cases.

Watch it run

The animation sorts [4, 1, 5, 2, 6, 3]. It starts by treating the first value as a sorted region of one, then absorbs the rest one at a time. It picks up 1 and leaves a gap: everything to its left is already sorted. Since 4 is bigger than 1, 4 slides one slot right and the gap moves left; the gap is then in the right place, 1 drops in, and the sorted region is two long. Picking up 5 takes no shifts at all, because 4 is not bigger. The 2 pushes 5 and then 4 one slot right before it drops in. The 6 again drops straight into its own gap. The last key, 3, has to pass 6, 5 and 4. The closing frame counts only 6 shifts in total, and points out that on nearly sorted data almost none happen, so the sort runs close to O(n).

The code

The lesson's version, with a shift counter added. The first result matches the animation's six shifts:

def insertion_sort(nums):
    shifts = 0
    for i in range(1, len(nums)):
        key = nums[i]
        j = i - 1
        while j >= 0 and nums[j] > key:    # strict >: equal values never pass each other
            nums[j + 1] = nums[j]          # slide the bigger value one slot right
            j -= 1
            shifts += 1
        nums[j + 1] = key                  # drop the key into the gap
    return nums, shifts

print(insertion_sort([4, 1, 5, 2, 6, 3]))     # ([1, 2, 3, 4, 5, 6], 6)
print(insertion_sort([1, 2, 3, 4, 5, 6]))     # ([1, 2, 3, 4, 5, 6], 0)
print(insertion_sort([6, 5, 4, 3, 2, 1]))     # ([1, 2, 3, 4, 5, 6], 15)

Shifts equal inversions. On 1,000 elements, two swapped pairs cost 6 shifts; a reversed list costs all 499,500 pairs:

def inversions(nums):
    return sum(1 for i in range(len(nums)) for j in range(i + 1, len(nums)) if nums[i] > nums[j])

print(inversions([4, 1, 5, 2, 6, 3]))         # 6

n = 1000
nearly = list(range(n))
nearly[10], nearly[11] = nearly[11], nearly[10]
nearly[500], nearly[503] = nearly[503], nearly[500]
for name, data in (("sorted", list(range(n))), ("nearly sorted", nearly),
                   ("reversed", list(range(n, 0, -1)))):
    print(name, insertion_sort(data)[1])
# sorted 0
# nearly sorted 6
# reversed 499500

Stability comes from the strict comparison. Sorting records by their second field keeps Ben before Di and Ada before Cy, the order they arrived in:

records = [("Ada", 3), ("Ben", 1), ("Cy", 3), ("Di", 1)]
def insertion_sort_by(items, key):
    for i in range(1, len(items)):
        item, j = items[i], i - 1
        while j >= 0 and key(items[j]) > key(item):
            items[j + 1] = items[j]
            j -= 1
        items[j + 1] = item
    return items

print(insertion_sort_by(records, key=lambda r: r[1]))
# [('Ben', 1), ('Di', 1), ('Ada', 3), ('Cy', 3)]

Finding the slot with binary search cuts the comparisons on a reversed list of 1,000 from 499,500 to 8,977, but list.insert still shifts every element after the slot, so the time stays O(n²):

def binary_insertion_sort(nums):
    compares = 0
    out = []
    for x in nums:
        lo, hi = 0, len(out)
        while lo < hi:                     # bisect_right, counted by hand
            mid = (lo + hi) // 2
            compares += 1
            if x < out[mid]:
                hi = mid
            else:
                lo = mid + 1
        out.insert(lo, x)                  # the shift is still O(n)
    return out, compares

print(binary_insertion_sort(list(range(1000, 0, -1)))[1])   # 8977

Checked against sorted() and the brute-force inversion count on 3,000 seeded random lists, with duplicates, empty lists and a stability check:

import random

random.seed(23)
ok = True
for _ in range(3000):
    data = [random.randint(-9, 9) for _ in range(random.randint(0, 25))]
    got, shifts = insertion_sort(list(data))
    ok &= got == sorted(data)
    ok &= shifts == inversions(data)
    ok &= binary_insertion_sort(data)[0] == sorted(data)
    tagged = [(v, i) for i, v in enumerate(data)]
    ok &= insertion_sort_by(list(tagged), key=lambda t: t[0]) == sorted(tagged, key=lambda t: t[0])
print(ok)                                     # True

The complexity

With n elements and I inversions:

• Time: O(n + I). That is O(n) on sorted input, O(n²) on reversed or random input, where about half of all pairs are inverted.
• Comparisons: at most n - 1 + I, one failed comparison per key plus one per shift.
• Space: O(1) extra. Only the key is held outside the array.
• Stable: yes, as long as the loop condition is a strict greater-than.

Where it goes wrong

• Using >= in the loop. It still sorts, but equal values jump past each other and the sort is no longer stable.
• Dropping the j >= 0 guard. In Python, nums[-1] reads the last element instead of failing, so the loop compares against the wrong value.
• Claiming binary search makes it O(n log n). It makes the comparisons O(n log n); the moves are still quadratic.
• Using it on large random data. Anything above a few dozen elements belongs to merge sort, quick sort or the library sort.

When it shows up in interviews

It comes up as a direct "implement a simple sort and give its best and worst case" question, and as a follow-up to bubble sort: which of the simple sorts would you actually use, and why? It is also the reason hybrid sorts switch to a simple sort on short runs, a point that fits into any discussion of merge sort versus quick sort. The inversion argument returns in problems that ask you to count inversions, usually with a merge sort variant.

How to say it in an interview

"I keep a sorted prefix. For each new element I lift it out, shift every bigger value in the prefix one slot right, and drop the element into the gap. Each shift fixes exactly one inversion, so the running time is O(n + inversions): O(n) for sorted input, O(n²) for reversed or random input. It sorts in place with O(1) extra space, and it is stable because I only shift on a strict greater-than. That low overhead is why library sorts use it for short runs, while anything large goes to an O(n log n) sort."