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

        # Shift elements greater than key to the right
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        # Insert key at its correct position
        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)):
        # Variable to keep the key
        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


# Sort students by grade
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

Case	Time Complexity	Description
Best case	O(n)	List is already sorted (only one comparison per element)
Average case	O(n²)	Elements are in random order
Worst case	O(n²)	List is sorted in reverse order (maximum shifts)
Space complexity	O(1)	Sorts in place, no extra memory needed

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}")


# Already sorted- best case
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:

tip

Use Insertion Sort when:

• The list is small (fewer than ~20-50 elements).
• The list is nearly sorted; Insertion Sort approaches O(n) performance.
• You need a stable sort (equal elements maintain their relative order).
• You need an online algorithm where elements can be sorted as they arrive.
• Memory is limited as it sorts in place with O(1) extra space.

info

Python's built-in sorted() and list.sort() use Timsort, which actually uses Insertion Sort internally for small subarrays (typically ≤ 64 elements) because of its low overhead and excellent performance on nearly sorted data.

Insertion Sort vs. Other Sorting Algorithms

Algorithm	Best	Average	Worst	Space	Stable
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	✅ Yes
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	❌ No
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	✅ Yes
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	✅ Yes
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	❌ No
Timsort	O(n)	O(n log n)	O(n log n)	O(n)	✅ Yes

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:

# Bug: key can never be placed at index 0
while j > 0 and arr[j] > key:  # Should be j >= 0
    arr[j + 1] = arr[j]
    j -= 1

arr = [3, 1, 2]
# With j > 0: produces [1, 3, 2] which is incorrect!
# With j >= 0: produces [1, 2, 3] which is correct!

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.