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

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.

• Start: [5, 2, 9, 1] — the first element (5) is trivially “sorted” on its own.
• i=1, key=2: compare with arr[0]=5. Since 5 > 2, shift 5 right: [5, 5, 9, 1]. No more elements to compare, insert 2 at position 0: [2, 5, 9, 1].
• i=2, key=9: compare with arr[1]=5. Since 5 < 9, no shift needed, insert 9 at position 2: [2, 5, 9, 1] (unchanged, since it was already correctly placed).
• i=3, key=1: compare with arr[2]=9, shift right: [2, 5, 9, 9]. Compare with arr[1]=5, shift right: [2, 5, 5, 9]. Compare with arr[0]=2, shift right: [2, 2, 5, 9]. No more elements, insert 1 at position 0: [1, 2, 5, 9].

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

• Worst case: O(n²) — occurs when the array is sorted in reverse order, since every new element needs to be compared against and shifted past every previously sorted element.
• Best case: O(n) — occurs when the array is already sorted, since the inner while loop’s condition (arr[j] > key) fails immediately for every element, requiring no shifting at all.
• Average case: O(n²) — for a randomly ordered array, roughly half of the previous elements need to be shifted for each new insertion on average.
• Space complexity: O(1) — insertion sort sorts in place, using only a constant amount of extra memory (key, i, j), regardless of input size.

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:

• Extremely efficient on nearly-sorted data. If an array is already mostly in order (common in real-world scenarios like inserting a few new records into an already-sorted dataset), insertion sort approaches its O(n) best case, often outperforming more complex algorithms that don’t specifically exploit existing order.
• Stable sort: elements with equal keys retain their original relative order, which matters when sorting by one attribute while wanting to preserve a previous ordering by another.
• In-place with O(1) extra space, unlike merge sort, which typically requires O(n) additional space for merging.
• Simple and low-overhead for very small arrays, where the constant-factor simplicity of insertion sort can actually outperform more complex algorithms whose overhead (recursive calls, partition logic) isn’t worth it for just a handful of elements.

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

• Sorting small datasets or small subarrays, where its low overhead outperforms more complex algorithms — exactly the role it plays inside Timsort.
• Online sorting, where data arrives one element at a time and needs to be kept in sorted order incrementally (inserting each new element into its correct position as it arrives, rather than re-sorting the whole collection).
• Nearly-sorted data scenarios, like maintaining a sorted list that receives occasional new entries close to their final position.
• Teaching sorting algorithm fundamentals, since insertion sort’s intuitive card-sorting analogy makes it an excellent first algorithm for understanding invariants, loop correctness, and complexity analysis.

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

• Print the array after each outer loop iteration (i) to see the “sorted so far” portion grow one element at a time — this visualization makes bugs in the shifting logic immediately apparent.
• Test with an already-sorted array, a reverse-sorted array, an array with duplicate values, and a single-element array — these cases together catch the overwhelming majority of implementation bugs.
• If using the custom key function variant, verify the key function itself in isolation before combining it with the sorting logic, to rule out bugs in key extraction versus bugs in the sort itself.

Performance Considerations

• Use insertion sort deliberately for small arrays or nearly-sorted data — this is a genuine, evidence-backed optimization, not just a toy exercise, given its role inside Timsort.
• For general-purpose sorting of arbitrary-sized, arbitrarily-ordered data in real applications, always prefer Python’s built-in sorted() or list.sort() over a hand-written insertion sort — the built-in is implemented in C and uses Timsort, which adapts its strategy based on the actual structure of the input data.
• If implementing insertion sort for educational or interview purposes, the binary-search-optimized variant demonstrates a deeper understanding of the trade-off between comparison count and shifting cost, even though it doesn’t change the overall worst-case complexity.

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

• Python official documentation: sorted() built-in function
• Python official documentation: Sorting HOWTO
• Python official documentation: bisect module
• CPython source repository documentation on the Timsort algorithm implementation, referenced via docs.python.org