Insertion Sort in Python Guide

Insertion sort is a simple sorting algorithm that builds the final sorted list one item at a time. It works the same way many people sort a hand of cards: keep the left side sorted, pick the next item, and insert it into the correct position.

In Python, insertion sort is most useful for learning algorithms, handling very small lists, or extending an already mostly sorted list. For normal application code, Python’s built-in list.sort() and sorted() are faster and should be your default choice. The official Python sorting HOWTO explains the built-in sorting tools.

How insertion sort works

Insertion sort divides the list into two parts:

• a sorted section on the left
• an unsorted section on the right

The first item is treated as already sorted. Then the algorithm takes each remaining item, compares it with the sorted section, shifts larger values one position to the right, and inserts the item where it belongs.

numbers = [8, 4, 6, 2]

A dry run looks like this:

• Start with [8] sorted.
• Insert 4 before 8: [4, 8, 6, 2].
• Insert 6 between 4 and 8: [4, 6, 8, 2].
• Insert 2 before everything: [2, 4, 6, 8].

Insertion sort algorithm

For a zero-indexed Python list, the algorithm is:

1. Start at index 1, because index 0 is already a sorted one-item section.
2. Store the current value in a temporary variable called key.
3. Move left while previous values are greater than key.
4. Shift each larger value one position to the right.
5. Place key into the open position.
6. Repeat until the end of the list.

Insertion sort Python code

This implementation sorts the list in place and returns the same list for convenience:

def insertion_sort(values):
    for index in range(1, len(values)):
        key = values[index]
        position = index - 1

        while position >= 0 and values[position] > key:
            values[position + 1] = values[position]
            position -= 1

        values[position + 1] = key

    return values


numbers = [8, 4, 6, 2, 9, 1]
print(insertion_sort(numbers))
# [1, 2, 4, 6, 8, 9]

This version shifts values instead of repeatedly swapping adjacent items. The result is the same, but the shifting version maps directly to the idea of making space for the current value.

If the range() boundaries look unfamiliar, review our guide to Python range behavior. In this loop, range(1, len(values)) starts at the second item and stops before len(values), which is exactly what we need.

Sort in descending order

To sort in descending order, reverse the comparison inside the while loop:

def insertion_sort_desc(values):
    for index in range(1, len(values)):
        key = values[index]
        position = index - 1

        while position >= 0 and values[position] < key:
            values[position + 1] = values[position]
            position -= 1

        values[position + 1] = key

    return values


print(insertion_sort_desc([8, 4, 6, 2]))
# [8, 6, 4, 2]

For everyday code, you can reverse a built-in sort with sorted(values, reverse=True). We also have a separate guide on reversing a Python list.

Insertion sort with a key function

Python's built-in sorting functions accept a key function. You can add the same idea to insertion sort for practice:

def insertion_sort_by_key(values, key=lambda item: item):
    for index in range(1, len(values)):
        current = values[index]
        current_key = key(current)
        position = index - 1

        while position >= 0 and key(values[position]) > current_key:
            values[position + 1] = values[position]
            position -= 1

        values[position + 1] = current

    return values


students = [
    {"name": "Ava", "score": 91},
    {"name": "Ben", "score": 84},
    {"name": "Mia", "score": 96},
]

print(insertion_sort_by_key(students, key=lambda student: student["score"]))

For real projects, prefer students.sort(key=lambda student: student["score"]). The list.sort() documentation describes the built-in method, and our guide on sorting a list of tuples in Python shows another common key-based sorting case.

Complexity of insertion sort

Insertion sort is stable when implemented with the comparison values[position] > key. Equal values are not moved ahead of each other, so their original order is preserved.

When should you use insertion sort?

Use insertion sort when you are learning algorithms, when the list is tiny, or when the data is nearly sorted and you want a simple in-place method. It is also useful to understand because Python's built-in sort, Timsort, takes advantage of already ordered runs in data. You can read more in our Python Timsort guide.

Do not use insertion sort as a replacement for built-in sorting in production code. Python's built-in sort is highly optimized in C and handles real-world data better. If you want to benchmark small examples, use the standard-library timeit module instead of timing code by eye.

Common mistakes

• Starting the outer loop at index 0 instead of index 1.
• Forgetting to store the current value before shifting other items.
• Using >= in the comparison and accidentally making the sort unstable for equal values.
• Expecting insertion sort to perform well on large random lists.
• Using insertion sort when list.sort() or sorted() would be clearer and faster.

Insertion sort vs other sorting algorithms

Insertion sort is easier to understand than many advanced algorithms, but it is not the fastest general-purpose option. If you are comparing sorting techniques, see our overview of sorting techniques in Python. Related algorithm guides include bubble sort in Python, counting sort in Python, and bitonic sort in Python.

Conclusion

Insertion sort in Python keeps a sorted section on the left and inserts each new value into that section. It is in-place, stable when written carefully, and easy to trace. Its main weakness is O(n^2) average and worst-case time, so use it for learning and small inputs, not as a general replacement for Python's built-in sorting tools.