Insertion Sort in Python
Sort the way you sort playing cards: take the next value and slide it left into place.
- Growing a sorted prefix
- Shifting larger values right
- Why it is fast on nearly sorted data
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.
current = result[index]🃏 Pick up the next cardresult[position] > current👈 Is the card on the left bigger?result[position + 1] = result[position]➡️ Slide the bigger card one place rightresult[position + 1] = current📥 Drop the card into the gapInsertion 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
for index in range(1, len(result)):starts at the second item; a single item is already sorted.currentholds the value being inserted while larger values move.while position >= 0 and result[position] > current:shifts each larger value one place right.result[position + 1] = currentdrops 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.insortfinds 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
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]))
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.
- Try empty, single-item, and duplicate-value inputs.
- Print state after every step to observe the algorithm.
- Benchmark 100, 1,000, and 10,000 items, then compare another approach.
Common mistakes
Writing current back inside the loop
The value must be placed once, after all larger values have moved.
while position >= 0 and result[position] > current:
result[position + 1] = result[position]
result[position] = current
position -= 1
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