AI Hints
Home›DSA in Python Tutorial›Better Sorts
DSA in Python · Lesson 52 of 132

Insertion Sort

Slide each item into place.

⏱ 2 min read▶ Video at 1:00:33🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Insertion sort works like adding cards to a hand you're already holding in order. Take the next card, and slide it left, past every bigger card, until it fits. It's O of N squared in general, but it's very fast when the list is almost sorted already.

Insertion Sort
From the video: Insertion Sort
  • Like cards in your hand
  • Slide each one left
  • Fast on nearly sorted lists

Sliding into place

We take each item, from the second one onward, and call it key. While the item to its left is bigger, we shift that item one place right. When we find a smaller item, or reach the start, the key drops into the gap. Run it. The sorted part on the left grows by one item each pass.

insertion.pypython
def insertion_sort(nums):
    for i in range(1, len(nums)):
        key = nums[i]
        j = i - 1
        while j >= 0 and nums[j] > key:
            nums[j + 1] = nums[j]
            j -= 1
        nums[j + 1] = key
        print(f"pass {i}: {nums}")

insertion_sort([5, 2, 9, 1, 7])
Output
pass 1: [2, 5, 9, 1, 7]
pass 2: [2, 5, 9, 1, 7]
pass 3: [1, 2, 5, 9, 7]
pass 4: [1, 2, 5, 7, 9]

Why insertion sort matters

On a nearly sorted list, each item only slides a step or two, so insertion sort is close to O of N. That's why real world sorting algorithms, including Python's own, use insertion sort for small pieces. It's also stable, meaning equal items keep their original order.

keyvalue
TimeO(n²), but O(n) if nearly sorted
SpaceO(1)
Stableequal items keep order
Used insidePython's own sort

Summary

Insertion sort slides each item left into place. It's great for small or nearly sorted lists. Next, a much faster idea. Merge sort.

Key takeaways
  • Take the next item
  • Slide it left
  • Great when nearly sorted
Next up: Merge Sort — divide and conquer