Python Program to Implement Insertion Sort

Sorting is an essential concept in programming, and understanding it is crucial for every beginner in Python. Among the various sorting algorithms, Insertion Sort is known for its simplicity and ease of learning. It is a great starting point for beginners because it works in a way similar to how we often organize cards in our hands—one card at a time, placing it in the correct position. Learning Insertion Sort gives you a solid foundation in algorithmic thinking and Python programming.

Insertion Sort is especially useful when you are dealing with small datasets or lists that are almost sorted, as it efficiently inserts elements into their proper position. While it is not the fastest sorting algorithm for large datasets, it helps beginners understand how to move elements step by step and implement comparisons, swaps, and iterations in Python code.

Program 1: Insertion Sort Using Loops

This program implements the classic loop-based approach to Insertion Sort. It iterates through the list, taking one element at a time and placing it in its correct position among the already sorted elements.

def insertion_sort(arr):

    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

    return arr


numbers = [12, 11, 13, 5, 6]

sorted_numbers = insertion_sort(numbers)

print("Sorted list:", sorted_numbers)

def insertion_sort(arr):

    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

    return arr


numbers = [12, 11, 13, 5, 6]

sorted_numbers = insertion_sort(numbers)

print("Sorted list:", sorted_numbers)

In this program, the key represents the element to be inserted in the correct position. The inner while loop shifts all larger elements one position ahead to make space for the key. This approach helps beginners understand the step-by-step process of insertion, making it easier to visualize how the list gradually becomes sorted.

Program 2: Insertion Sort in Descending Order

Sometimes, we need to sort a list from largest to smallest. This version of Insertion Sort modifies the comparison to insert each element in descending order.

def insertion_sort_desc(arr):

    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

    return arr


numbers = [20, 35, 15, 10, 40]

sorted_numbers = insertion_sort_desc(numbers)

print("Sorted list in descending order:", sorted_numbers)

def insertion_sort_desc(arr):

    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

    return arr


numbers = [20, 35, 15, 10, 40]

sorted_numbers = insertion_sort_desc(numbers)

print("Sorted list in descending order:", sorted_numbers)

This version works similarly to the ascending order version, but it compares elements in reverse, ensuring the largest elements move to the front. Beginners can see how simply changing the comparison operator can control the sorting order, making the algorithm adaptable for different needs.

Program 3: Insertion Sort Using Recursion

Insertion Sort can also be implemented recursively. This approach inserts one element at a time and uses recursion to sort the remaining portion of the list.

def recursive_insertion_sort(arr, n=None):

    if n is None:
        n = len(arr)

    if n <= 1:
        return arr

    recursive_insertion_sort(arr, n-1)

    last = arr[n-1]
    j = n-2

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

        arr[j + 1] = arr[j]
        j -= 1

    arr[j + 1] = last

    return arr


numbers = [9, 5, 1, 4, 3]

sorted_numbers = recursive_insertion_sort(numbers)

print("Sorted list using recursion:", sorted_numbers)

def recursive_insertion_sort(arr, n=None):

    if n is None:
        n = len(arr)

    if n <= 1:
        return arr

    recursive_insertion_sort(arr, n-1)

    last = arr[n-1]
    j = n-2

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

        arr[j + 1] = arr[j]
        j -= 1

    arr[j + 1] = last

    return arr


numbers = [9, 5, 1, 4, 3]

sorted_numbers = recursive_insertion_sort(numbers)

print("Sorted list using recursion:", sorted_numbers)

In this recursive version, the function first sorts the first n-1 elements and then inserts the last element into its proper position. This approach is helpful for beginners to understand recursion and see how an iterative process can be translated into a recursive one, reinforcing algorithmic thinking in Python.

Program 4: Insertion Sort Using a Key Function

Python’s flexibility allows sorting with a key function, similar to Java’s comparator. This approach is useful for custom sorting logic, such as sorting strings by length or tuples by a specific index.

def insertion_sort_key(arr, key_func):

    for i in range(1, len(arr)):

        key_item = arr[i]
        j = i - 1

        while j >= 0 and key_func(arr[j]) > key_func(key_item):

            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key_item


words = ["apple", "banana", "kiwi", "cherry"]

insertion_sort_key(words, key_func=len)

print("Sorted by length:", words)

def insertion_sort_key(arr, key_func):

    for i in range(1, len(arr)):

        key_item = arr[i]
        j = i - 1

        while j >= 0 and key_func(arr[j]) > key_func(key_item):

            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key_item


words = ["apple", "banana", "kiwi", "cherry"]

insertion_sort_key(words, key_func=len)

print("Sorted by length:", words)

Using a key function teaches beginners how to adapt the algorithm to different data types or custom sorting rules without changing the core logic.

Program 5: Insertion Sort for Objects

Insertion Sort can also sort complex objects. In this example, we sort a list of Person objects by age.

class Person:

    def __init__(self, name, age):
        self.name = name
        self.age = age

    def __repr__(self):
        return f"{self.name} ({self.age})"


def insertion_sort_objects(arr):

    for i in range(1, len(arr)):

        key_person = arr[i]
        j = i - 1

        while j >= 0 and arr[j].age > key_person.age:

            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key_person


people = [Person("Mary", 25), Person("Samantha", 20), Person("Mary", 30)]

insertion_sort_objects(people)

print("Sorted by age:", people)

class Person:

    def __init__(self, name, age):
        self.name = name
        self.age = age

    def __repr__(self):
        return f"{self.name} ({self.age})"


def insertion_sort_objects(arr):

    for i in range(1, len(arr)):

        key_person = arr[i]
        j = i - 1

        while j >= 0 and arr[j].age > key_person.age:

            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key_person


people = [Person("Mary", 25), Person("Samantha", 20), Person("Mary", 30)]

insertion_sort_objects(people)

print("Sorted by age:", people)

This example demonstrates how Insertion Sort can be applied to real-world data. Beginners gain experience combining object-oriented programming with algorithmic thinking.

Frequently Asked Questions (FAQ)

Insertion Sort often brings up common questions for beginners. Here are some answers to help you understand it better.

Q1: Is Insertion Sort efficient for large datasets?
Insertion Sort has a time complexity of O(n²), so it is suitable for small or nearly sorted datasets. For large datasets, algorithms like Quick Sort or Merge Sort are faster.

Q2: Can I sort objects with Insertion Sort?
Yes, by comparing object attributes, you can sort objects, making the algorithm practical for real-world scenarios.

Q3: Why use recursion in Insertion Sort?
Recursion helps learners understand problem decomposition. While iterative solutions are more practical, recursion is great for teaching algorithmic thinking.

Q4: Can I sort in descending order?
Absolutely. Adjust the comparison in the loop to reverse the order.

Q5: How does a key function work in Python sorting?
A key function allows you to define custom sorting rules for any data type without modifying the algorithm’s core logic.

Conclusion

Insertion Sort is a fundamental algorithm that provides beginners with a strong foundation in sorting and algorithmic thinking. By exploring iterative, recursive, key-function-based, and object-oriented versions, learners can understand the algorithm from multiple perspectives. Practicing these variations strengthens skills in loops, comparisons, recursion, and object manipulation. The best way to master Insertion Sort is to experiment with different datasets, observe the sorting process, and gradually build confidence in algorithm design.