Implementing a Custom Sorting Algorithm in Python

Introduction

Sorting is one of the most common tasks in programming, forming the backbone of many data processing and optimization routines. While Python’s built-in sorted() function and the list.sort() method are highly optimized, there’s immense educational value in understanding how sorting works under the hood. In this post, we’ll explore step-by-step how to implement the insertion sort algorithm, one of the simplest sorting algorithms, purely in Python. Along the way, we’ll visualize each iteration and discuss performance implications and optimization tips.

1. Understanding the Concept of Insertion Sort

Insertion sort works similarly to sorting playing cards in your hand. You take one card at a time and insert it into its correct position relative to the already sorted portion. The algorithm divides the list into two parts: a sorted part (on the left) and an unsorted part (on the right). We repeatedly take an element from the unsorted side and insert it into the sorted side in the correct position.

Example: [5, 2, 4, 6, 1, 3]

Step 1: Start with the second element (2). Compare it with 5. Since 2 < 5, move 5 to the right and insert 2 at the start → [2, 5, 4, 6, 1, 3]

Step 2: Next element (4). Compare 4 with 5, move 5 right, insert 4 → [2, 4, 5, 6, 1, 3]

The process continues until all elements are inserted correctly.

2. Implementing Insertion Sort Step-by-Step in Python

Let’s code our insertion sort function from scratch while adding print statements to show each iteration. This helps visualize what the algorithm is doing internally.

def insertion_sort(arr):
    # Traverse from the second element to the end
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # Move elements of arr[0..i-1], that are greater than key, one position ahead
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
        print(f"Iteration {i}: {arr}")

# Example usage
numbers = [5, 2, 4, 6, 1, 3]
insertion_sort(numbers)
print("Sorted Array:", numbers)

Each loop prints the array’s state after inserting one element into the sorted portion. This visualization helps developers see how elements move and where they are inserted.

3. Visualizing Each Iteration

Imagine we run the code above. The printed output will show something like:

Iteration 1: [2, 5, 4, 6, 1, 3]
Iteration 2: [2, 4, 5, 6, 1, 3]
Iteration 3: [2, 4, 5, 6, 1, 3]
Iteration 4: [1, 2, 4, 5, 6, 3]
Iteration 5: [1, 2, 3, 4, 5, 6]

You can visualize these transitions by plotting them using libraries like matplotlib, where the array’s index positions are on the x-axis and their values on the y-axis, updating after each iteration. This makes it easier to comprehend how gradual ordering happens.

import matplotlib.pyplot as plt
import time

def visualize_insertion_sort(arr):
    plt.ion()
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
        plt.clf()
        plt.bar(range(len(arr)), arr, color='skyblue')
        plt.title(f"Iteration {i}")
        plt.draw()
        plt.pause(0.5)
    plt.show()

visualize_insertion_sort([5, 2, 4, 6, 1, 3])

This produces a simple animation showing bars shifting as the array becomes sorted—a useful teaching aid.

4. Complexity and Performance Considerations

Insertion sort shines when dealing with small datasets or nearly sorted lists. However, for large datasets, its performance degrades quickly. Understanding its time complexity helps in deciding when to use it:

Best case: O(n) — when the array is already sorted
Average case: O(n²)
Worst case: O(n²)

The space complexity of insertion sort is O(1), as it sorts in-place without extra data structures. Hence, it’s a good choice for memory-limited environments or when the dataset is nearly sorted (e.g., real-time incremental sorting of small batches).

5. Optimization and Real-World Uses

While insertion sort isn’t the fastest, it has practical uses:

Efficient for small data sets or partially sorted lists (like in hybrid algorithms such as Timsort used by Python).
Can be implemented in systems with tight memory constraints.
Useful in educational tools and algorithm visualization apps.

If you want to optimize it slightly, consider breaking early if no shifting occurs during an iteration:

def optimized_insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        swapped = False
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
            swapped = True
        arr[j + 1] = key
        if not swapped:
            break
    return arr

Small optimizations like this can save cycles when the list is already nearly sorted.

Conclusion

Insertion sort’s beauty lies in its simplicity and step-by-step predictability. Implementing it manually provides valuable insights into algorithm design, data movement, and optimization strategy. By understanding how it works internally, developers can appreciate Python’s built-in sorting and know when to apply this educational yet practical algorithm in real-world scenarios.

Useful links: