Understanding Insertion Sort: From Basics to Implementation

Table of Contents

Insertion sort is a simple, intuitive sorting algorithm that builds the final sorted array (or list) one item at a time. Despite being less efficient on large lists compared to more advanced algorithms like QuickSort or MergeSort, its simplicity and the fact that it performs well on small or partially sorted datasets make it a valuable algorithm to understand and utilize.

How Insertion Sort Works

Imagine you’re organizing a deck of cards in your hands. You start with the second card and compare it to the first. If it’s smaller, you place it before the first card, otherwise, you leave it in place. At this point, the first one or two cards are considered sorted. You then move on to the third card, inserting it into the correct position among the already sorted cards. This process of sorting and insertion divides the deck into two sections: the left side, which becomes increasingly sorted as you insert cards into their correct positions, and the right side, which remains unsorted until you pick up each card to sort.

With each card you move from the unsorted section (the cards still in your right hand) to the sorted section (the cards being organized in your left hand), you’re effectively reducing the unsorted portion and increasing the sorted portion. By the time you reach the last card, the unsorted section is empty, and your deck is fully sorted in your left hand.

This process mimics the insertion sort algorithm. Here’s a step-by-step breakdown:

Initialization: At the start, the sorted section consists of only the first element of the array, and the rest of the array is considered unsorted.
Sorting the current element: Begin with the second element (the first element in the unsorted section). Compare this current element to its predecessor in the sorted section. If the current element is smaller than its predecessor, continue comparing it to the elements before, moving each compared element one position up to make space for the current element.
Inserting in the sorted section: Once the correct position in the sorted section is identified, insert the current element and thus, extend the sorted section by one more element.
Repeat for each element: Continue this process for each element in the array. For each new element in the unsorted section, insert it into the correct position within the sorted section until no unsorted elements remain.

Insertion Sort Example.

Implementation

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

This Python code implements the Insertion Sort algorithm, which sorts an array in ascending order. Here’s a breakdown explaining the purpose of each variable and the overall process:

arr: This is the input array that contains the elements to be sorted. It is both the input and the output of the function, as the sorting is done in-place.
i: This variable is used as the index for the outer loop. It starts from 1, indicating the start of the unsorted section of the array. The element at arr[i] is the one currently being inserted into the sorted portion of the array.
key: This variable holds the value of the element currently being sorted. It’s temporarily saved so that it can be inserted into its correct position within the sorted portion of the array.
j: This variable is used in the inner loop to compare the current element (key) with each of the elements in the sorted section of the array (arr[0] to arr[i-1]). It helps in finding the correct position for key by shifting larger elements one position to the right.

Complexity Analysis

Complexity Type	Time Complexity
Best Case	$O(n^2)$
Average Case	$O(n^2)$
Worst Case	$O(n^2)$
Space Complexity	$O(1)$

Summary complexity table for insertion sort

Runtime Complexity

Insertion sort has a time complexity of $O(n^2)$ in its best, average and worst-case scenarios.

For each element, in the worst case, it compares it with each of the previously sorted elements. This results in a maximum of 1 comparison for the second element, 2 for the third, and so on, up to $n-1$ comparisons for the last element.

The total work done can be summed up as the sum of the first $n-1$ integers, which is $1+2+3+...+n-1=\frac{n(n−1)}{2}$ . In big O notation, the dominating term is $n^2$ , leading to a complexity of $O(n^2)$ .

The $O(n^2)$ complexity makes insertion sort less efficient for sorting large arrays compared to algorithms with better time complexities, such as QuickSort or MergeSort, which offer $O(nlogn)$ average time complexity.

Space Complexity

Insertion sort has a space complexity of $O(1)$ , making it an in-place sorting algorithm. This means it requires a constant amount of additional space regardless of the input size. The algorithm achieves this by performing the sorting operation directly on the input array, without the need for additional storage structures. The only extra space used is for a small number of variables to hold the current element being considered for insertion and indices for tracking positions within the array.

Conclusion

In conclusion, Insertion Sort stands out for its simplicity, and its in-place sorting mechanism with a minimal space complexity of $O(1)$ .
While its $O(n^2)$ time complexity may limit its use for large datasets, its straightforward process of building a sorted array one element at a time, offers a tangible and intuitive approach to sorting that is especially useful for beginners learning about algorithms.