Insertion Sort

Given an unsorted array, rearrange it in ascending order. Insertion sort builds the sorted portion one element at a time. It picks the first element from the unsorted portion, shifts larger elements in the sorted portion right by one, and inserts the picked element into the gap.

This is exactly how you sort a hand of playing cards: you pick up one card at a time and insert it where it belongs among the cards you already hold.

One Deep Walkthrough: [8, 5, 2, 9, 1]

The first element (8) is trivially sorted. We pick from index 1 onward.

Step 1 — pick key = arr[1] = 5

The sorted portion is [8]. Compare 5 with 8. Since 8 > 5, shift 8 right by one position.

Step 2 — pick key = arr[2] = 2

Compare with 8 → shift. Compare with 5 → shift.

Step 3 — pick key = arr[3] = 9

Compare with 8. 8 > 9? No. Stop immediately. Insert key at index 3 (its original position).

Step 4 — pick key = arr[4] = 1

Compare with 9 → shift. Compare with 8 → shift. Compare with 5 → shift. Compare with 2 → shift.

Code

def insertion_sort(arr):
    n = len(arr)

    for i in range(1, n):
        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

Line by line:

• for i in range(1, n): — start from index 1. Index 0 is the initial sorted portion.
• key = arr[i] — save the element to be inserted. Without saving it, the shifts would overwrite it.
• j = i - 1 — start comparing from the rightmost element of the sorted portion.
• while j >= 0 and arr[j] > key: — shift condition. If the sorted element is greater than key, it must move right. The j >= 0 guard prevents accessing index -1.
• arr[j + 1] = arr[j] — shift the element right by one position.
• j -= 1 — move one position left to check the next sorted element.
• arr[j + 1] = key — insert key at the gap. j + 1 is correct because j was decremented after the last shift (or never moved if no shift occurred).

Edge case — already sorted. The while condition arr[j] > key is always false. The inner loop never executes. arr[j + 1] = key writes key back to its own position (no-op). The array is scanned once. O(n).

Edge case — all identical. arr[j] > key is never true (equal is not greater). Zero shifts. O(n).

Time: O(n²) average and worst. O(n) best. Space: O(1).

Stability: Insertion sort is stable — equal elements keep their relative order because the shift stops at > (strictly greater), not >=.

Code Trace

Tracing insertion_sort([8, 5, 2, 9, 1]):

Insertion sort is the best O(n²) sort for nearly-sorted data. Python's Timsort uses it for small subarrays. It is adaptive (O(n) best case), stable, and has low overhead.

→ LeetCode 147: Insertion Sort List — the linked list version.