Offensive Security Researcher & Quantum Cryptography Analyst

Develop a Function to Implement Insertion Sort: Complete Python Sorting Algorithm and Implementation

Abdul Wahab Junaid
Develop a function to implement Insertion Sort

Develop a function to implement Insertion Sort

I think of insertion sort every time I sort a hand of playing cards — I pick up each new card and slide it into its correct position among the cards I’m already holding, rather than laying everything out and comparing all of them at once. That’s genuinely the entire algorithm, and it’s part of why I find insertion sort the most intuitive sorting algorithm to actually explain to someone new to programming. Here’s the complete implementation guide, from the basic version through the internal mechanics and performance trade-offs.

The Core Idea

Insertion sort builds a sorted portion of the array one element at a time, taking each new element and inserting it into its correct position relative to the already-sorted portion — exactly like sorting a hand of cards.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

numbers = [5, 2, 9, 1, 5, 6]
print(insertion_sort(numbers))  # [1, 2, 5, 5, 6, 9]

Walking Through the Algorithm Step by Step

Let me trace through [5, 2, 9, 1] manually, since seeing exactly what happens at each iteration is the best way to internalize this algorithm.

Final result: [1, 2, 5, 9] — sorted correctly.

Why the while Loop Condition Matters

while j >= 0 and arr[j] > key:

Both conditions here are essential, and Python’s short-circuit evaluation of and is actually doing meaningful work: j >= 0 is checked first, so if j becomes -1 (meaning we’ve shifted past the beginning of the array), Python never evaluates arr[j] > key at all — avoiding an IndexError from accessing arr[-1]… wait, actually arr[-1] in Python is valid (it wraps to the last element!), which makes this condition ordering even more critical than it might first appear. If the conditions were reversed (arr[j] > key and j >= 0), a j value of -1 would silently compare against the last element of the array due to Python’s negative indexing, producing subtly wrong behavior rather than a clean crash — a genuinely sneaky bug that’s specific to how Python indexing works.

Sorting in Descending Order

def insertion_sort_descending(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] < key:  # flipped comparison
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

print(insertion_sort_descending([5, 2, 9, 1, 5, 6]))  # [9, 6, 5, 5, 2, 1]

Flipping the single comparison operator (> to <) is all that’s needed to reverse the sort order — a nice illustration of how much of the algorithm’s behavior is governed by that one comparison.

Sorting With a Custom Key Function

Real-world sorting often needs to sort complex objects by a specific attribute rather than comparing them directly.

def insertion_sort_by_key(arr, key_func):
    for i in range(1, len(arr)):
        current = arr[i]
        current_key = key_func(current)
        j = i - 1
        while j >= 0 and key_func(arr[j]) > current_key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = current
    return arr

people = [{"name": "Carol", "age": 45}, {"name": "Alice", "age": 30}, {"name": "Bob", "age": 17}]

sorted_people = insertion_sort_by_key(people, key_func=lambda p: p["age"])
print([p["name"] for p in sorted_people])  # ['Bob', 'Alice', 'Carol']

I’d note that calling key_func() repeatedly inside the inner loop, as written above, recomputes the key value every single comparison — for an expensive key function, precomputing keys once (similar to how Python’s own sorted() handles its key parameter internally, computing each key exactly once via a technique sometimes called a Schwartzian transform) would be a meaningful optimization.

Time and Space Complexity

import time
import random

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# Best case: already sorted
already_sorted = list(range(5000))
start = time.perf_counter()
insertion_sort(already_sorted.copy())
print(f"Already sorted: {time.perf_counter() - start:.4f}s")

# Worst case: reverse sorted
reverse_sorted = list(range(5000, 0, -1))
start = time.perf_counter()
insertion_sort(reverse_sorted.copy())
print(f"Reverse sorted: {time.perf_counter() - start:.4f}s")

Running this yourself makes the O(n) vs O(n²) difference between best and worst case genuinely visible — the reverse-sorted case takes dramatically longer than the already-sorted case, even though both have the same number of elements.

Why Insertion Sort Is Genuinely Useful Despite O(n²)

It’s tempting to write off insertion sort as strictly inferior to O(n log n) algorithms like merge sort or Timsort (Python’s actual built-in sort), but it has real, specific advantages:

This last point isn’t just theoretical — it’s exactly why Python’s actual built-in sorting algorithm, Timsort, uses insertion sort internally as a subroutine for small runs (subsequences) of data, typically below a threshold of around 64 elements, before applying its more sophisticated merge-based logic on larger runs. Insertion sort isn’t just an academic stepping stone; it’s a genuinely used component of one of the most widely deployed sorting algorithms in the world.

Optimized Version Using Binary Search for Insertion Position

A clever variant finds the correct insertion position using binary search (since the “already sorted” portion is, by definition, sorted) rather than a linear scan, though this doesn’t reduce the overall shifting cost.

import bisect

def binary_insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        pos = bisect.bisect_left(arr, key, 0, i)
        arr[pos + 1:i + 1] = arr[pos:i]
        arr[pos] = key
    return arr

print(binary_insertion_sort([5, 2, 9, 1, 5, 6]))  # [1, 2, 5, 5, 6, 9]

This reduces the number of comparisons from O(n) to O(log n) per insertion (using binary search to find the position), but the actual shifting of elements to make room is still O(n) per insertion in the worst case, since Python list slicing still has to move every shifted element — so the overall worst-case time complexity remains O(n²), even though the comparison count itself is meaningfully reduced.

Real-World Applications

Common Mistakes

Getting the while loop’s shift-and-decrement logic wrong, causing elements to be overwritten incorrectly or the key to be inserted at the wrong final position — this is the most common source of bugs in a hand-rolled implementation.

Assuming insertion sort is always a bad choice because of O(n²) worst case, overlooking its genuine strengths on small or nearly-sorted data — dismissing it entirely misses real practical value.

Forgetting insertion sort is stable, and not leveraging that property when it matters (e.g., sorting by a secondary key while preserving a previous sort by a primary key).

Reinventing insertion sort for general-purpose sorting in production code instead of using Python’s built-in sorted() or list.sort(), which use the highly optimized Timsort algorithm (itself partially built on insertion sort’s ideas, but far more sophisticated overall).

Debugging Tips

Performance Considerations

FAQs

Is insertion sort stable? Yes — elements with equal keys are never swapped past each other, since the inner loop only shifts elements strictly greater than the key, preserving the relative order of equal elements.

Why does Python’s built-in sorted() use insertion sort at all if it’s O(n²)? Timsort, Python’s actual sorting algorithm, uses insertion sort specifically for small subarrays (typically under ~64 elements), where its low constant-factor overhead outperforms more complex algorithms — and it always applies its full merge-based strategy for larger overall inputs, so the O(n²) risk never applies to large-scale sorting in practice.

How does insertion sort compare to bubble sort? Both are O(n²) in the worst case, but insertion sort is generally considered more efficient in practice, since it makes fewer total comparisons and swaps on average, and it explicitly exploits existing partial order in the data, unlike a naive bubble sort implementation.

When should I actually use insertion sort instead of Python’s built-in sort? Almost never for general-purpose sorting in production code — use it primarily for educational purposes, for genuinely tiny fixed-size datasets where its simplicity has real value, or as a documented, deliberate building block within a larger custom algorithm.

Summary

Insertion sort builds a sorted result one element at a time, inserting each new element into its correct position among the already-sorted portion — an algorithm as intuitive as sorting a hand of playing cards. Its O(n²) worst-case complexity makes it unsuitable for large, arbitrarily-ordered datasets in general-purpose use, but its O(n) best case on nearly-sorted data, its stability, and its low overhead on small inputs are genuinely valuable properties — valuable enough that Python’s own built-in Timsort algorithm uses insertion sort internally for small subarrays. Understanding it thoroughly, including its subtle implementation pitfalls around loop bounds and comparison order, is foundational to understanding sorting algorithms as a whole.

References

Exit mobile version