Insertion sort explained: how it works, code and complexity

The idea in plain words

Treat the first element as a sorted list of length one. Take the second element and insert it before or after the first. Take the third element and insert it into the right place among the first two. Continue until every element has been inserted.

To insert, hold the new element aside (call it key), then walk left through the sorted part. Every element larger than key moves one position right. When you reach an element that is not larger, or the start of the list, put key in the empty slot.

Worked example, step by step

Sort [12, 11, 13, 5, 6]. The part before the bar is sorted (but not yet final).

Notice step 2: an element that is already in place costs a single comparison. That is why insertion sort is fast on nearly sorted input.

Python implementation

def insertion_sort(items):
    """Sort a list in place, ascending. Returns the same list."""
    for i in range(1, len(items)):
        key = items[i]
        j = i - 1
        while j >= 0 and items[j] > key:   # strict >, keeps it stable
            items[j + 1] = items[j]        # shift right
            j -= 1
        items[j + 1] = key                 # drop into the gap
    return items
print(insertion_sort([12, 11, 13, 5, 6]))   # [5, 6, 11, 12, 13]
print(insertion_sort([1, 2, 3, 4]))         # [1, 2, 3, 4], 3 comparisons

Shifting instead of swapping writes each moved element once, which is about half the work of the swap-based version. You can also find the insertion point with binary search, as below. This reduces comparisons to O(n log n) in total, but the shifts are still O(n²), so the overall time stays O(n²).

from bisect import insort_right
def binary_insertion_sort(items):
    result = []
    for x in items:
        insort_right(result, x)   # stable: equal items go after
    return result
print(binary_insertion_sort([3, 1, 2, 1]))   # [1, 1, 2, 3]

Time and space complexity

More precisely, the running time is O(n + I), where I is the number of inversions (pairs out of order). If every element is at most k positions from its final place, I is at most n · k, so insertion sort is O(n · k): very fast when k is small.

How insertion sort compares with other sorts

Insertion sort is stable because an element only moves left past elements that are strictly greater. It is also online: it can sort data as it arrives, keeping a sorted prefix at every moment. For short lists, its low overhead beats O(n log n) algorithms, so Timsort (used by Python and by Java for objects) sorts short runs with binary insertion sort, and many quicksort implementations switch to insertion sort below a small size.

Variants and common mistakes

• Binary insertion sort: binary search for the position, then shift. Fewer comparisons, which helps when comparing is expensive.
• Shell sort: run insertion sort on elements a gap apart, then shrink the gap down to 1. It moves far-away elements quickly and is much faster than plain insertion sort on large arrays.
• Linked-list insertion sort: no shifting is needed, but finding the position is still a linear scan.

When to use insertion sort

Use it for small arrays (tens of elements), for data that is nearly sorted, such as a list that was sorted and then had a few items appended, and when you need a simple stable in-place sort. For large random data, use an O(n log n) sort; in Python that means sorted() or list.sort(), which already apply insertion sort to small runs internally.

Interview questions often ask for the trace, the best and worst cases, why it is stable, or why it beats O(n log n) algorithms on small and nearly sorted input.