Python insertion sort

Grow a sorted prefix by shifting larger elements.

Python

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

print(insertion_sort([3, 1, 2]))
assert insertion_sort([]) == []
assert insertion_sort([2, 2, 1]) == [1, 2, 2]

Output

[1, 2, 3]

Explanation

Insertion sort maintains a sorted prefix to the left of the current position. Save the current value as key, shift larger prefix values right, then fill the gap.

Using > rather than >= preserves the relative order of equal values, making this implementation stable. The function copies its input so callers keep the original list.

Explore the dry run

Guided walkthroughReady

1def insertion_sort(values):

2 result = values.copy()

3 for i in range(1, len(result)):

4 key = result[i]

5 j = i - 1

6 while j >= 0 and result[j] > key:

7 result[j + 1] = result[j]

8 j -= 1

9 result[j + 1] = key

10 return result

12print(insertion_sort([3, 1, 2]))

13assert insertion_sort([]) == []

14assert insertion_sort([2, 2, 1]) == [1, 2, 2]

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Copy the input.	`result = [3, 1, 2]`	—
First pass selects 1.	`i = 1, key = 1, j will be 0`	—
Shift 3 right.	`result = [3, 3, 2]`	—
Place 1 in the gap at index 0.	`result = [1, 3, 2]`	—
Second pass selects 2.	`i = 2, key = 2`	—
Shift 3 right; stop before 1.	`result = [1, 3, 3]`	—
Insert 2 at index 1.	`result = [1, 2, 3]`	—
Print the sorted copy.	`result = [1, 2, 3]`	[1, 2, 3]

Cost and common mistakes

O(n²) worst-case time, O(n) best-case time, O(n) auxiliary space here because of the copy.

Save key before shifting, or its original value is lost.
Check j >= 0 before reading result[j]; Python accepts negative indices.

Try it yourself

Trace [2, 1, 1].

Reveal answer and reasoning

After pass one: [1, 2, 1]. After pass two: [1, 1, 2]. Equal ones keep their original relative order.

Python insertion sort

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading