How to Implement Insertion Sort Algorithm in Python

Insertion Sort is a simple and intuitive sorting algorithm that builds a sorted list one element at a time. It works similarly to how you might sort a hand of playing cards: you pick up each card and insert it into its correct position among the cards you've already sorted.

While not the most efficient algorithm for large datasets, Insertion Sort is an excellent choice for small lists, nearly sorted data, and as a building block in more advanced algorithms like Timsort (Python's built-in sort). In this guide, you will learn how Insertion Sort works, see a clear Python implementation, and understand its performance characteristics.

How Insertion Sort Works

The algorithm divides the list into two portions: a sorted portion (initially just the first element) and an unsorted portion (the rest). It then repeatedly takes the next element from the unsorted portion and inserts it into the correct position in the sorted portion.

Step-by-step process:

1. Start from the second element (index 1), since a single element is already "sorted."
2. Store the current element as the key.
3. Compare the key with elements in the sorted portion (moving right to left).
4. Shift all elements greater than the key one position to the right.
5. Insert the key into its correct position.
6. Repeat until the entire list is sorted.

Visual Walkthrough

Initial:  [12, 11, 13, 5, -1]

Step 1:   key=11  → [11, 12, 13, 5, -1]    (11 inserted before 12)
Step 2:   key=13  → [11, 12, 13, 5, -1]    (13 stays in place)
Step 3:   key=5   → [5, 11, 12, 13, -1]    (5 inserted at beginning)
Step 4:   key=-1  → [-1, 5, 11, 12, 13]    (-1 inserted at beginning)

Result:   [-1, 5, 11, 12, 13]

Python Implementation

def insertion_sort(arr):
    n = len(arr)

    for i in range(1, n):
        key = arr[i]          # Element to be inserted
        j = i - 1

        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key


arr = [12, 11, 13, 5, -1]
insertion_sort(arr)
print(arr)

Output:

[-1, 5, 11, 12, 13]

Code explanation:

• for i in range(1, n): Iterates through the list starting from the second element.
• key = arr[i]: Stores the current element that needs to be placed in the sorted portion.
• while j >= 0 and arr[j] > key: Moves backward through the sorted portion, shifting larger elements one position to the right.
• arr[j + 1] = key: Places the key in its correct sorted position after the shifting is complete.

Step-by-Step Trace with Output

To better understand the algorithm, here's a version that prints each step:

def insertion_sort_verbose(arr):
    n = len(arr)

    for i in range(1, n):
        key = arr[i]
        j = i - 1

        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key
        print(f"Step {i}: key={key:>3} → {arr}")


arr = [12, 11, 13, 5, -1]
print(f"Start:          {arr}")
insertion_sort_verbose(arr)
print(f"Sorted:         {arr}")

Output:

Start:          [12, 11, 13, 5, -1]
Step 1: key= 11 → [11, 12, 13, 5, -1]
Step 2: key= 13 → [11, 12, 13, 5, -1]
Step 3: key=  5 → [5, 11, 12, 13, -1]
Step 4: key= -1 → [-1, 5, 11, 12, 13]
Sorted:         [-1, 5, 11, 12, 13]

Sorting in Descending Order

To sort in descending order, simply change the comparison operator from > to <:

def insertion_sort_desc(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        while j >= 0 and arr[j] < key:  # Changed > to <
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key


arr = [12, 11, 13, 5, -1]
insertion_sort_desc(arr)
print(arr)

Output:

[13, 12, 11, 5, -1]

Sorting Custom Objects

Insertion Sort can sort any comparable objects. Here's an example sorting a list of tuples by the second element:

def insertion_sort_key(arr, key_func):
    """Insertion sort with a custom key function."""
    for i in range(1, len(arr)):
        key_item = arr[i]
        key_val = key_func(key_item)
        j = i - 1

        while j >= 0 and key_func(arr[j]) > key_val:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key_item


students = [("Alice", 88), ("Bob", 75), ("Carol", 92), ("Dave", 65)]
insertion_sort_key(students, key_func=lambda x: x[1])

print("Sorted by grade:")
for name, grade in students:
    print(f"  {name}: {grade}")

Output:

Sorted by grade:
  Dave: 65
  Bob: 75
  Alice: 88
  Carol: 92

Time and Space Complexity

Why O(n) Best Case?

When the list is already sorted, the inner while loop never executes because arr[j] is never greater than key. Each element requires only one comparison, resulting in O(n) total comparisons:

def insertion_sort_verbose(arr):
    n = len(arr)

    for i in range(1, n):
        key = arr[i]
        j = i - 1

        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key
        print(f"Step {i}: key={key:>3} → {arr}")


arr = [1, 2, 3, 4, 5]
insertion_sort_verbose(arr)

Output:

Step 1: key=  2 → [1, 2, 3, 4, 5]
Step 2: key=  3 → [1, 2, 3, 4, 5]
Step 3: key=  4 → [1, 2, 3, 4, 5]
Step 4: key=  5 → [1, 2, 3, 4, 5]

No elements are shifted because only comparisons are made.

When to Use Insertion Sort

Insertion Sort is the right choice in specific scenarios:

Insertion Sort vs. Other Sorting Algorithms

Common Mistake: Off-by-One in the Inner Loop

A frequent error is using j > 0 instead of j >= 0 in the while condition, which prevents the key from being inserted at index 0:

Wrong:

while j > 0 and arr[j] > key:  # Should be j >= 0
    arr[j + 1] = arr[j]
    j -= 1

arr = [3, 1, 2]

Correct:

while j >= 0 and arr[j] > key:
    arr[j + 1] = arr[j]
    j -= 1

Summary

Insertion Sort is a fundamental sorting algorithm that every programmer should understand. Key takeaways:

• How it works: Pick each element and insert it into its correct position in the already-sorted portion of the list.
• Best case O(n): Extremely efficient for nearly sorted data.
• Worst/average case O(n²): Not suitable for large, randomly ordered datasets.
• In-place and stable: Uses O(1) extra space and preserves the order of equal elements.
• Practical use: Excellent for small lists and used internally by Python's Timsort for small subarrays.

For production code with large datasets, use Python's built-in sorted() or list.sort(). For small lists, educational purposes, or nearly sorted data, Insertion Sort remains a practical and elegant choice.