Python Algorithms

Insertion Sort in Python

Sort the way you sort playing cards: take the next value and slide it left into place.

  • Intermediate
  • 2 min read
  • 1 runnable example
What you'll learn
  • Growing a sorted prefix
  • Shifting larger values right
  • Why it is fast on nearly sorted data
Inserting 4 into [1, 5, 9]
1stays
4inserted
5shifted →
9shifted →
3next
Start: [9, 5, 1, 4, 3]. Result: [1, 3, 4, 5, 9].

Insert each value into the sorted part

The problem

Data often arrives nearly sorted, or one item at a time: a sorted list of scores gets one new score. Re-sorting everything is wasteful. Insertion sort handles this case very well and is how many people sort playing cards by hand.

Think of it like this

Insertion sort is how you sort cards in your hand. You pick up one card at a time and slide it left past every bigger card until it sits in the right place. The cards to the left of it are always in order.

From sorting cards to code
current = result[index]🃏 Pick up the next card
result[position] > current👈 Is the card on the left bigger?
result[position + 1] = result[position]➡️ Slide the bigger card one place right
result[position + 1] = current📥 Drop the card into the gap
The left part is always sorted; each new item is inserted into it.
In one sentence

Insertion sort builds a sorted part one item at a time by shifting larger items right and inserting the current item into the gap; it is O(n²) in the worst case but close to O(n) on nearly sorted data.

Key points

  1. for index in range(1, len(result)): starts at the second item; a single item is already sorted.
  2. current holds the value being inserted while larger values move.
  3. while position >= 0 and result[position] > current: shifts each larger value one place right.
  4. result[position + 1] = current drops the value into the gap that was opened.

When should you use it?

  • Small or nearly sorted lists.
  • Keeping a list sorted as new items arrive.
  • As the final step inside faster sorts, which switch to insertion sort for small pieces.

When not to use it

  • Large random lists: the shifting becomes slow, so use sorted().
  • Inserting into a big sorted list often: bisect.insort finds the position with binary search.

Insertion Sort in Python visualizer

O(n²)

Use Play or Step to follow each comparison and data movement.

Example code

Run code →
main.py
def insertion_sort(values):
    result = values.copy()
    for index in range(1, len(result)):
        current = result[index]
        position = index - 1
        while position >= 0 and result[position] > current:
            result[position + 1] = result[position]
            position -= 1
        result[position + 1] = current
    return result

print(insertion_sort([9, 5, 1, 4, 3]))
Get a Run button for this example

Result of running the code

[1, 3, 4, 5, 9]

Code explanation

Larger prefix values shift right until the current value reaches its correct position. Worst-case time complexity is O(n²).

Change the values and run the program in the CodeUtility online Python compiler without installing Python locally.

Practice exercises

Modify the runnable example with the exercises below to build understanding beyond copying the result.

  1. Try empty, single-item, and duplicate-value inputs.
  2. Print state after every step to observe the algorithm.
  3. Benchmark 100, 1,000, and 10,000 items, then compare another approach.
Run in the Python compiler →

Common mistakes

Writing current back inside the loop

The value must be placed once, after all larger values have moved.

Problem
while position >= 0 and result[position] > current:
    result[position + 1] = result[position]
    result[position] = current
    position -= 1
Fix
while position >= 0 and result[position] > current:
    result[position + 1] = result[position]
    position -= 1
result[position + 1] = current

Finished this lesson?

Mark it as learned to track your progress.

Practice with a challenge

Use what this lesson covers to solve a real problem. Each challenge runs in your browser with instant tests and an AI review.

All challenges