Insertion Sort

Insertion sort is a simple, comparison-based sorting algorithm that builds a sorted portion of an array one element at a time, the same way many people sort a hand of playing cards. Each new element is picked up and inserted into its correct position among the already-sorted elements to its left, shifting larger elements one slot to the right to make room. It is rarely the fastest option for large datasets, but it is easy to reason about, stable, adaptive to nearly-sorted input, and it even shows up as a building block inside Python’s own hybrid sort, Timsort.

Overview: How Insertion Sort Works

Picture sorting a hand of playing cards. You hold one card — trivially "sorted" on its own — then pick up the next card and slide it into the correct spot among the cards you’re already holding, comparing it against your held cards from right to left until you find where it belongs. You repeat this for every new card until the whole hand is sorted. Insertion sort applies the exact same idea to an array. It treats the first element as a sorted subarray of length one, then repeatedly takes the next element (traditionally called the key) and shifts it leftward past every already-sorted element that is greater than it, stopping as soon as it finds an element that is smaller or equal, or it runs out of elements to compare against.

The key invariant is this: after the algorithm finishes processing index i in the outer loop, the subarray arr[0:i+1] is fully sorted, even though the rest of the array (arr[i+1:]) has not been touched yet. This is why insertion sort is called an in-place and online algorithm — it can sort a stream of incoming values by inserting each new value into the correct position of what has already been sorted, without needing to see the whole dataset up front.

Concretely, the algorithm looks like this: for each index i from 1 to len(arr) - 1, save arr[i] as key, then walk a pointer j backward from i - 1, shifting arr[j] one position to the right as long as arr[j] > key and j hasn’t gone below 0. When the inner loop stops, the gap left behind is exactly where key belongs, so it’s written to arr[j + 1].

Time and Space Complexity

Insertion sort’s performance depends heavily on how sorted the input already is, which is what makes it "adaptive." The inner while loop does the real work: in the worst case it shifts every prior element, and in the best case it does no shifting at all.

Case	Time	Why
Best (already sorted)	O(n)	For every i, the very first comparison arr[j] > key is false, so the inner loop exits immediately. Only n - 1 comparisons happen in total, no shifts.
Average (random order)	O(n2 — roughly n2/4 comparisons)	On average, a new element needs to move about halfway back through the sorted prefix, so the total work grows quadratically with n.
Worst (reverse sorted)	O(n2	Every new element is smaller than everything before it, so it must shift all the way to index 0. Total comparisons/shifts sum to 1 + 2 + ... + (n - 1) = n(n - 1)/2, which is O(n2.

Space complexity is O(1) auxiliary space: the algorithm sorts the array in place using only a constant number of extra variables (key, i, j), regardless of n. This is a real practical advantage over algorithms like merge sort, which typically need O(n) extra space for merging.

Examples

Example 1: Basic ascending sort

The most direct implementation sorts a list of integers in place.

def insertion_sort(arr: list[int]) -> list[int]:
    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
    return arr


def main() -> None:
    numbers = [12, 11, 13, 5, 6]
    print("Before:", numbers)
    insertion_sort(numbers)
    print("After:", numbers)


if __name__ == "__main__":
    main()

Output:

Before: [12, 11, 13, 5, 6]
After: [5, 6, 11, 12, 13]

Tracing it: at i=1, key=11 shifts past 12, giving [11, 12, 13, 5, 6]. At i=2, key=13 doesn’t need to move. At i=3, key=5 shifts past 13, 12, and 11, landing at index 0: [5, 11, 12, 13, 6]. At i=4, key=6 shifts past 13, 12, and 11, stopping because 5 < 6, giving the final sorted array [5, 6, 11, 12, 13].

Example 2: Sorting by key, and proving stability

A stable sort preserves the relative order of elements that compare equal. Insertion sort is stable because the inner loop only shifts elements that are strictly greater than the key — it never shifts past an equal element, so two equal elements never swap places relative to each other.

from typing import Callable


def insertion_sort_by_key(
    items: list[tuple[str, int]], key: Callable[[tuple[str, int]], int]
) -> list[tuple[str, int]]:
    for i in range(1, len(items)):
        current = items[i]
        current_key = key(current)
        j = i - 1
        while j >= 0 and key(items[j]) > current_key:
            items[j + 1] = items[j]
            j -= 1
        items[j + 1] = current
    return items


records = [("Alice", 85), ("Bob", 92), ("Cara", 85), ("Dan", 78)]
sorted_records = insertion_sort_by_key(records, lambda r: r[1])
print(sorted_records)

Output:

[('Dan', 78), ('Alice', 85), ('Cara', 85), ('Bob', 92)]

Alice (score 85) appears before Cara (score 85) in both the input and the output, even though they tie on the sort key. That’s stability in action — useful when you sort by one field but want ties to keep their original relative order (for example, sorting log entries by severity while preserving their original chronological order among entries of the same severity).

Example 3: Insertion sort is adaptive

Because the inner loop exits as soon as it finds an element that doesn’t need to move, insertion sort does much less work on data that’s already close to sorted. This example counts comparisons to make that concrete.

def insertion_sort_with_counter(arr: list[int]) -> tuple[list[int], int]:
    comparisons = 0
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            comparisons += 1
            arr[j + 1] = arr[j]
            j -= 1
        if j >= 0:
            comparisons += 1
        arr[j + 1] = key
    return arr, comparisons


nearly_sorted = [1, 2, 4, 3, 5]
result, comparisons = insertion_sort_with_counter(nearly_sorted)
print("Sorted:", result)
print("Comparisons:", comparisons)

Output:

Sorted: [1, 2, 3, 4, 5]
Comparisons: 5

With n=5, a reverse-sorted array would need n(n-1)/2 = 10 comparisons, but this nearly-sorted array only needs 5 — close to the theoretical best case of n - 1 = 4. Only the misplaced 4 and 3 require any shifting at all.

How It Works Step by Step

Trace insertion sort on [8, 4, 6, 2] by hand:

Step	Key	What happens	Array after step
i = 1	4	8 > 4, so 8 shifts right; 4 lands at index 0	[4, 8, 6, 2]
i = 2	6	8 > 6 shifts right; 4 > 6 is false, so 6 lands at index 1	[4, 6, 8, 2]
i = 3	2	8, then 6, then 4 all shift right; 2 lands at index 0	[2, 4, 6, 8]

Each row shows the subarray to the left of the current index staying sorted the entire time — that’s the loop invariant that makes the algorithm correct.

Common Mistakes

Mistake 1: Off-by-one in the inner loop condition

A very common bug is writing while j > 0 instead of while j >= 0. This means index 0 is never compared against, so an element that belongs at the very front of the array can get stuck one position too late.

def insertion_sort_buggy(arr: list[int]) -> list[int]:
    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
    return arr


numbers = [3, 1]
print(insertion_sort_buggy(numbers))

Output:

[3, 1]

With arr = [3, 1], at i=1 the loop condition j > 0 is immediately false because j starts at 0 — so arr[0] = 3 is never compared against key = 1, and the array is returned completely unsorted. The fix is using j >= 0 so index 0 is always eligible for comparison:

def insertion_sort_fixed(arr: list[int]) -> list[int]:
    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
    return arr


numbers = [3, 1]
print(insertion_sort_fixed(numbers))

Output:

[1, 3]

Mistake 2: Forgetting insertion sort mutates its input in place

Because Python lists are passed by reference, sorting arr in place also mutates whatever list the caller passed in — even though the function also returns it. If the caller expected to keep an untouched copy of the original data, this is a nasty surprise.

def insertion_sort(arr: list[int]) -> list[int]:
    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
    return arr


original = [5, 3, 1]
sorted_version = insertion_sort(original)
print("original:", original)
print("sorted_version:", sorted_version)
print("same object:", original is sorted_version)

Output:

original: [1, 3, 5]
sorted_version: [1, 3, 5]
same object: True

Notice original got sorted too, and original is sorted_version is True — they’re literally the same list object. If you need to preserve the original, copy it first with arr.copy() (or list(arr)) before sorting:

def insertion_sort_copy(arr: list[int]) -> list[int]:
    arr = arr.copy()
    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
    return arr


original = [5, 3, 1]
sorted_version = insertion_sort_copy(original)
print("original:", original)
print("sorted_version:", sorted_version)

Output:

original: [5, 3, 1]
sorted_version: [1, 3, 5]

Best Practices

• Use insertion sort for small arrays (roughly n < 20–50) where its low constant-factor overhead beats the setup cost of an O(n log n) algorithm.
• Reach for it when data arrives incrementally (an online/streaming scenario) since it naturally extends a sorted prefix one element at a time.
• Prefer it when the input is known to be nearly sorted — its adaptive best case of O(n) makes it very efficient there, unlike algorithms with a fixed O(n log n) regardless of input order.
• Choose it when stability matters and simplicity is more valuable than raw speed on large n.
• For real production code sorting anything but tiny or special-cased data, use Python’s built-in sorted() or list.sort(), which use Timsort — a hybrid algorithm that actually runs insertion sort internally on small runs, then merges those runs efficiently.
• Avoid hand-rolling insertion sort for large, randomly ordered datasets; its O(n2 average case will be noticeably slower than O(n log n) alternatives as n grows.

Practice Exercises

• Descending sort: Modify insertion_sort so it sorts a list of integers in descending order instead of ascending. Hint: flip the comparison in the while condition. For input [4, 2, 7, 1], expect [7, 4, 2, 1].
• Shift counter as a "sortedness" metric: Write a function that returns the total number of shifts insertion sort performs on a given array, without actually needing to know the array’s contents beforehand. Then compare the shift count for [1, 2, 3, 4, 5] (already sorted) versus [5, 4, 3, 2, 1] (reverse sorted). Expect 0 shifts for the first and 10 shifts for the second.
• Binary insertion sort: Insertion sort’s inner loop does a linear scan to find where key belongs, but since arr[0:i] is already sorted, you can use binary search (see bisect.bisect_left) to find the insertion index in O(log n) instead. Implement this variant. Note that this reduces the number of comparisons, but shifting elements to make room is still O(n) per insertion, so the overall worst-case time complexity remains O(n2.

Summary

• Insertion sort builds a sorted prefix of the array one element at a time, inserting each new element into its correct position by shifting larger elements rightward.
• Time complexity: O(n) best case (already sorted), O(n2 average and worst case (random or reverse-sorted input).
• Space complexity: O(1) auxiliary — it sorts in place.
• It is stable (equal elements keep their relative order) and adaptive (faster on nearly-sorted input) and online (can insert new elements as they arrive).
• Common bugs: using j > 0 instead of j >= 0 in the inner loop (skips index 0), and forgetting that sorting in place mutates the caller’s original list because Python passes list references, not copies.
• In practice, use Python’s built-in sorted()/list.sort() (Timsort) for real sorting needs; insertion sort is best for small or nearly-sorted data, or as a teaching example of an adaptive, stable, in-place sort.