Course information
B2.4.3 · Sorting

Insertion sort · extension

Python · step by step

Insertion sort · extension

Watch the list change while following the actual Python execution.

Select Play or Next line to follow Python execution.

Python implementation

The highlight marks the next line to execute. Values show the state before that line.

def insertion_sort(items):    for i in range(1, len(items)):        key = items[i]        j = i - 1        while j >= 0 and items[j] > key:            items[j + 1] = items[j]            j = j - 1        items[j + 1] = key    return items

Optional extension, not one of the two named B2.4.3 sorts. Keep key aside while shifting larger values; the prefix grows in sorted order. O(n) best-case and O(n²) worst-case time; O(1) auxiliary space.

Keep exploring

Return to the sorting lesson →

All B2.4 animations →

All practice & resources →