Insertion Sort in Python

Sorting is an important concept in programming and data structures. A sorting algorithm arranges elements in a particular order, usually ascending or descending. Insertion Sort in Python is one of the simplest sorting algorithms and is especially useful for small or nearly sorted datasets.

Insertion Sort works similarly to arranging playing cards in your hand. You take one element at a time and place it in its correct position among the elements that are already sorted.

In this tutorial, we will learn what Insertion Sort is, how it works, how to implement it in Python, how to sort custom objects, and how to understand its time and space complexity.

Complete Advance AI Topics: Click Here
SQL Tutorial: Click Here

What is Insertion Sort?

Insertion Sort is an in-place and stable sorting algorithm. It builds the sorted portion of a list one element at a time. Each new element is compared with the elements before it and inserted into its appropriate position.

Insertion Sort is particularly useful when the dataset is small or when the elements are already close to being sorted.

Key Properties of Insertion Sort

• In-place: It sorts the elements within the original list and requires very little additional memory.
• Stable: Equal elements maintain their relative order.
• Simple: The algorithm is easy to understand and implement.
• Adaptive: It can perform well when the input list is nearly sorted.
• Useful for small datasets: It can be practical when the number of elements is small.

How Does Insertion Sort Work?

Insertion Sort divides the list conceptually into two parts:

1. Sorted Part: Initially contains the first element.
2. Unsorted Part: Contains the remaining elements.

The algorithm takes the first element from the unsorted part and compares it with the elements in the sorted part. Larger elements are shifted one position to the right, and the selected element is inserted into the correct position.

Steps of Insertion Sort

1. Consider the first element as already sorted.
2. Select the next element from the unsorted portion.
3. Compare it with the elements in the sorted portion.
4. Shift larger elements one position to the right.
5. Insert the selected element into its correct position.
6. Repeat the process until all elements are sorted.

Insertion Sort Example

Consider the following unsorted list:

[10, 4, 25, 1, 5]

The sorting process works as follows:

1. 10 is considered sorted.
2. 4 is smaller than 10, so 10 is shifted and 4 is placed before it.
3. 25 is greater than the sorted elements, so it remains at the end.
4. 1 is smaller than the existing elements, so the larger elements are shifted right and 1 is inserted at the beginning.
5. 5 is inserted between 4 and 10.

The final sorted list is:

[1, 4, 5, 10, 25]

Insertion Sort in Python

We can implement Insertion Sort using a function and a for loop.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        value = arr[i]
        j = i - 1

        while j >= 0 and value < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = value

    return arr


arr = [10, 5, 13, 8, 2]

print("Unsorted List:", arr)
print("Sorted List:", insertion_sort(arr))

Output

Unsorted List: [10, 5, 13, 8, 2]
Sorted List: [2, 5, 8, 10, 13]

Explanation of the Python Program

Let’s understand the important parts of the program:

• The insertion_sort() function accepts the list as an argument.
• The for loop starts from index 1 because the first element is treated as sorted.
• The current element is stored in the variable value.
• The while loop compares the current value with previous elements.
• When a previous element is larger, it is shifted one position to the right.
• After finding the correct position, the current value is inserted there.
• The process continues until the entire list is sorted.

Insertion Sort Using a For Loop

Insertion Sort naturally uses a for loop to process each element. The inner while loop is responsible for shifting larger elements.

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

for i in range(1, len(numbers)):
    current = numbers[i]
    j = i - 1

    while j >= 0 and numbers[j] > current:
        numbers[j + 1] = numbers[j]
        j -= 1

    numbers[j + 1] = current

print(numbers)

Output

[1, 3, 4, 5, 9]

Sorting Custom Objects Using Insertion Sort

Insertion Sort can also be used with custom objects. For example, we can create a Point class and sort points according to their x coordinate.

def insertion_sort(arr, compare_func):
    for i in range(1, len(arr)):
        value = arr[i]
        j = i - 1

        while j >= 0 and compare_func(arr[j], value):
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = value


class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __str__(self):
        return f"({self.x}, {self.y})"


points = [
    Point(2, 3),
    Point(4, 4),
    Point(3, 1),
    Point(8, 0),
    Point(5, 2)
]

insertion_sort(points, lambda a, b: a.x > b.x)

for point in points:
    print(point)

Output

(2, 3)
(3, 1)
(4, 4)
(5, 2)
(8, 0)

Here, the comparison function checks the x coordinate of each object and places the points in ascending order.

Time Complexity of Insertion Sort

The time required by Insertion Sort depends on how the elements are arranged before sorting.

Case	Time Complexity
Best Case	O(n)
Average Case	O(n²)
Worst Case	O(n²)

The best case occurs when the list is already sorted or nearly sorted. The worst case generally occurs when the elements are arranged in reverse order.

Space Complexity

Insertion Sort has a space complexity of O(1) because it sorts the list in place and does not require another list for storing the sorted elements.

Advantages of Insertion Sort

• Simple and easy to implement.
• Works efficiently for small datasets.
• Performs well on nearly sorted data.
• It is a stable sorting algorithm.
• It is an in-place sorting algorithm.
• Requires only O(1) additional space.

Limitations of Insertion Sort

• It can be inefficient for large datasets.
• Its average and worst-case time complexity is O(n²).
• Large numbers of shifts and comparisons may be required.

YT:- DecodeIT

Conclusion

Insertion Sort in Python is a simple and useful sorting algorithm that builds a sorted list one element at a time. It works by selecting an element, shifting larger elements, and inserting the selected value into its correct position.

It is especially useful for small or nearly sorted datasets. Although its average and worst-case complexity is O(n²), its simplicity, stability, and in-place operation make it an important algorithm to learn when studying sorting and data structures.

Frequently Asked Questions

What is Insertion Sort in Python?

Insertion Sort is a sorting algorithm that builds the sorted portion of a list one element at a time by inserting each element into its correct position.

What is the time complexity of Insertion Sort?

The best-case complexity is O(n), while the average and worst-case complexity is O(n²).

Is Insertion Sort stable?

Yes. Insertion Sort is a stable sorting algorithm when implemented in its standard form.

Is Insertion Sort suitable for large datasets?

Insertion Sort is generally more suitable for small or nearly sorted datasets. Its O(n²) average and worst-case complexity can make it inefficient for large unsorted datasets.

What is the space complexity of Insertion Sort?

Insertion Sort has O(1) auxiliary space complexity because it sorts the elements within the original list.

Keywords

Insertion Sort in Python, insertion sort algorithm, insertion sort in Python with example, insertion sort in Python using list, insertion sort in Python using for loop, insertion sort in Python user input, insertion sort in Python without using function, insertion sort in Python W3Schools, Python insertion sort program, insertion sort example, insertion sort implementation in Python, insertion sort time complexity, insertion sort space complexity, selection sort in Python, sorting algorithms in Python