Insertion SortInsertion sort

01Why it exists

Reach for it when you see:Small arrays (a few dozen at most), nearly sorted data, every element close to its final position, items arriving one at a time that must stay ordered, a stable in-place sort, the small runs inside a hybrid sort.

02The core idea

Insertion sort is how you tidy a hand of playing cards: your left hand holds a pile that is already in order, and each new card you draw gets slotted in by scanning right to left for the spot it belongs. On an array, that means splitting it into a sorted region a[0..i-1] on the left and the untouched part on the right. Each round saves a[i] into key, which leaves a "hole" where it used to sit. Looking left, every element larger than key shifts one slot right and the hole follows it leftwards, until you hit the first element that is not larger than key (or run off the left end) and drop key into the hole.

Correctness rests on a loop invariant: before round i, a[0..i-1] is exactly the first i original elements in sorted order. Everything shifted during the round is larger than key, and the whole block moves right together, so their relative order is untouched. The position j where the loop stops satisfies a[j] ≤ key, and everything to its left is ≤ a[j], so once key lands at j+1 the region a[0..i] is still sorted. Run that through i = n−1 and the whole array is sorted. Because it shifts only on a strictly greater comparison, key never crosses an element equal to it, which makes insertion sort stable; and since it needs just one extra temporary, it sorts in place.

For complexity, counting the shifts is enough. Every shift removes exactly one inversion (the pair of key and the element it just passed), so the total shift count equals the array's inversion count I. Each round adds at most one more comparison, the one that fails and stops the loop, so comparisons fall between I and I + (n−1) and the total time is O(n + I). On sorted input I = 0 and only n−1 comparisons happen, the best case of O(n); on fully reversed input I = n(n−1)/2, the worst case of O(n²); on random data the expected inversion count is n(n−1)/4, so the average is still O(n²). If no element sits more than k slots from its final position, no element shifts left more than k times, and the time becomes O(nk). Extra space is O(1).

Three mistakes come up again and again. The loop condition must include j >= 0, and it must come before a[j] > key: in C++, dropping it or swapping the order reads out of bounds at a[-1], while in Python a[-1] is a perfectly legal "last element", so a missing check may raise an IndexError or, worse, silently scramble the data. Writing >= instead of > lets equal elements cross each other and throws away stability. Swapping instead of shifting gives the same answer, but turns one write per step into three — and what you have built is really bubble sort's adjacent swapping. Against the neighbours: bubble sort performs exactly as many swaps as there are inversions, but insertion sort writes only once per step; selection sort always spends n(n−1)/2 comparisons no matter what the data looks like, whereas insertion sort speeds up on its own as the input gets tidier (it is adaptive). It is also an online algorithm, keeping the data ordered as items arrive one at a time. Merge sort and quicksort both switch to it on small runs, and generalising "shift by one" into "shift by gap" gives you shell sort.

03The algorithm

1. 1The outer loop runs i from 1 to n−1. At the start of round i, a[0..i-1] is already sorted; it begins as just a[0], and a single element is sorted by itself.
2. 2Save a[i] into key and set j = i − 1. Slot a[i] is now a hole, so overwriting it loses nothing.
3. 3while j >= 0 and a[j] > key: a[j+1] = a[j], j -= 1. Test j >= 0 first, and shift only on a strictly greater comparison — that is what keeps the sort stable.
4. 4The loop stops with a[j] ≤ key or j = −1. Write key into a[j+1], and the sorted region grows to a[0..i].
5. 5When comparisons are expensive, use bisect_right (upper_bound) to locate the insertion point inside a[0..i-1] and shift the block in one go. To run it on a hybrid sort's small runs, replace the left bound 0 with the run's start lo.

04Interactive demo

The shared array is [5, 2, 9, 1, 7, 3, 8, 4]. Each round lifts one element into the hand, leaving a dashed hole behind it. Green is the sorted region, amber is the element just compared with the card in hand (if it is larger it shifts one slot right and the hole moves left), and blue is where the card was just inserted. Notice that inserting 9 stops after a single comparison, while inserting 1 shifts all the way to the left end. The run ends with 13 shifts, exactly this array's inversion count. There are 18 comparisons: the 13 shifts plus the 5 comparisons that stopped the loop (inserting 2 and 1 ran off the left end, so those rounds need no stopping comparison), which sits right inside the range I to I + (n−1) = 20.

05Code

The basic version plus two variants. Binary insertion sort cuts comparisons to O(n log n) while the moves stay O(n²), which pays off for expensive strings or objects — it is what Timsort uses. In C++ that means std::upper_bound to find the slot and one std::rotate to shift the block. The range version sorts only a[lo..hi], the shape a hybrid sort calls on its small runs.

from bisect import bisect_right


# Insertion sort: a[0..i-1] is already sorted. Lift a[i], shift everything larger one slot right, drop it in the hole.
def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]                          # the card in hand; a[i] is now a hole
        j = i - 1
        while j >= 0 and a[j] > key:        # strictly greater, so equals never cross: stable
            a[j + 1] = a[j]                 # shift one slot right, the hole moves left
            j -= 1
        a[j + 1] = key                      # drop it into the hole
    return a


# Variant 1: binary insertion sort.
# Binary search finds the slot, so comparisons drop to O(n log n); the moves are still O(n²). Good when comparing is expensive.
def binary_insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        pos = bisect_right(a, key, 0, i)    # land to the right of equal elements: stable
        a[pos + 1:i + 1] = a[pos:i]         # shift the whole block one slot right
        a[pos] = key
    return a


# Variant 2: sort only a[lo..hi] (both ends inclusive).
# A hybrid sort calls this once a run gets small, instead of recursing further.
def insertion_sort_range(a, lo, hi):
    for i in range(lo + 1, hi + 1):
        key = a[i]
        j = i - 1
        while j >= lo and a[j] > key:       # the left bound is lo, not 0
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key


if __name__ == "__main__":
    print(insertion_sort([5, 2, 9, 1, 7, 3, 8, 4]))                  # [1, 2, 3, 4, 5, 7, 8, 9]
    print(binary_insertion_sort(["pear", "fig", "apple", "kiwi"]))  # ['apple', 'fig', 'kiwi', 'pear']
    b = [9, 8, 7, 6, 5, 4, 3, 2, 1]
    insertion_sort_range(b, 2, 6)                                    # sorts indices 2..6 only
    print(b)                                                         # [9, 8, 3, 4, 5, 6, 7, 2, 1]

06Practice

• LeetCode 2418Sort the People (hand-write insertion sort, moving names along with heights)Easy
• LeetCode 147Insertion Sort List (a linked list needs no shifting, but you scan from the head)Medium
• LeetCode 57Insert Interval (find the slot in a sorted list, then merge the overlaps)Medium
• LeetCode 775Global and Local Inversions (when nothing is more than one slot off, every inversion is adjacent)Medium
• LeetCode 1649Create Sorted Array through Instructions (the cost of each insertion, sped up with a BIT)Hard