Python Program for Insertion Sort

Sorts a list by taking each item in turn and inserting it into its place among the sorted items before it.

Insertion sort works the way many people sort a hand of cards: take the next card and slide it left past every bigger card until it's in place. The items before the current one are always sorted, and each step inserts one more item among them. In [27, 38, 43, 3, 9, 82, 10], inserting 3 means moving 43, 38 and 27 one place right and putting 3 at the front.

Program

def insertion_sort(items):
    """Sort items in place, from smallest to largest."""
    for i in range(1, len(items)):
        current = items[i]
        j = i - 1
        # Move each bigger item one place right to make room
        while j >= 0 and items[j] > current:
            items[j + 1] = items[j]
            j -= 1
        items[j + 1] = current


numbers = [38, 27, 43, 3, 9, 82, 10]
print("Before:", numbers)
insertion_sort(numbers)
print("After: ", numbers)

Open in the editor Download insertion_sort.py

Output

Before: [38, 27, 43, 3, 9, 82, 10]
After:  [3, 9, 10, 27, 38, 43, 82]

How it works

Visualize Step through the program line by line: each step below shows up as its line runs.

1. The loop takes each item in turn, from the second to the last. The items before index i are already sorted: at the start that's only the first item, and one item on its own is always sorted.
2. current keeps the item to insert, because the shifting below writes over its place. j starts at the item before it.
3. While the item at j is bigger than current, it moves one place right and j steps left. j >= 0 stops the loop at the start of the list, when current is the smallest item so far.
4. The loop has stopped at an item no bigger than current, or gone past the start, so current goes into the gap after it, at j + 1.
5. The program prints the list, sorts it in place, and prints it again.

The list after each item is inserted:

Time and space complexity

The work depends on how far each item has to move. In the worst case, a list in reverse order, every item moves past all the items before it: 1 + 2 + … + (n − 1) = n(n − 1)/2 moves, which is O(n²). In the best case, a list that's already sorted, the while test fails straight away for every item, so the sort takes O(n) time. The sample list needs 11 moves, one for each pair of items in the wrong order. That's why insertion sort is fast on short or nearly sorted lists, and Python's own sort uses it for short stretches of a list. It sorts in place with a few variables, so the extra space is O(1). It is stable: the while loop stops at an item equal to current, so the new item goes after it and equal items keep their order.

Other ways to write it

With swaps

Instead of moving the bigger items right and writing current once at the end, this version swaps the new item left one place at a time. It's shorter, but each swap writes two items, so it does about twice the writing.

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

numbers = [38, 27, 43, 3, 9, 82, 10]
insertion_sort(numbers)
print(numbers)

With the bisect module

insort() from the bisect module puts an item into a sorted list at its place, finding the place by binary search. Building a new list with it is insertion sort in a few lines, though making room for each item still moves the items after it (modules).

from bisect import insort

def insertion_sort(items):
    result = []
    for item in items:
        insort(result, item)
    return result

print(insertion_sort([38, 27, 43, 3, 9, 82, 10]))

Try it yourself

• Print the list after each item is inserted and compare it with the table above.
• Sort a list that's already sorted and one in reverse order, and count how many items move right for each.
• Sort from largest to smallest by changing one comparison.
• Sort a list of words, such as ["pear", "apple", "fig", "kiwi"]: strings compare in alphabetical order.

More searching and sorting programs

• Python Program for Bubble Sort Beginner
• Python Program for Linear Search Beginner
• Python Program for Selection Sort Beginner
• Python Program for Binary Search Intermediate
• Python Program for Merge Sort Intermediate
• Python Program for Quick Sort Intermediate