Python · Course navigation

Python insertion sort

Grow a sorted prefix by shifting larger elements.

On this page

Before you start

Lists, indexing, and nested loops.

Grow a sorted prefix by shifting larger elements.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

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.

Code example

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]

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

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]

Behind the scenes

How Python processes this code

Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.

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.