Insertion Sort

November 1, 2022

Coding & Algorithm Interview  Data Structures & Algorithms 

Introduction

Sorting is a fundamental operation in computer programming, and there are many algorithms available for this purpose. One popular and simple sorting algorithm is Insertion Sort. It’s a comparison-based sorting algorithm that works by dividing the dataset into two parts: a sorted part and an unsorted part. The algorithm repeatedly takes an element from the unsorted part and inserts it into its correct position within the sorted part. In this tech blog, we will explore the details of Insertion Sort, how it works, its advantages and disadvantages, and its implementation in code.

How Does Insertion Sort Work?

Insertion Sort is a simple algorithm that iterates through the dataset and “inserts” each element into its correct position within the sorted part of the dataset. The algorithm starts with the first element and considers it as the sorted part. It then takes the next element from the unsorted part, compares it with the elements in the sorted part, and shifts the elements to the right until it finds the correct position for the element being inserted. This process is repeated until the entire dataset is sorted.

Here’s a step-by-step breakdown of how Insertion Sort works:

1. Start with the second element in the dataset (assuming the first element is already sorted).
2. Compare it with the elements in the sorted part of the dataset from right to left.
3. If the element is smaller, shift the elements to the right to make space for the element being inserted.
4. Repeat step 3 until the correct position for the element is found.
5. Move to the next unsorted element and repeat steps 2-4.
6. Continue this process until the entire dataset is sorted.

Advantages of Insertion Sort

1. Simplicity: Insertion Sort is a simple algorithm that is easy to understand and implement. It serves as a good choice for small datasets or as an educational tool for beginners to learn about sorting algorithms.
2. Adaptive: Insertion Sort performs well on partially sorted datasets, as it requires fewer comparisons and swaps compared to other sorting algorithms. It can efficiently sort datasets that are already partially sorted.
3. Space Complexity: Insertion Sort has a space complexity of O(1), as it only requires a constant amount of additional space to store temporary variables for swapping and comparisons.

Disadvantages of Insertion Sort

1. Time Complexity: Insertion Sort has a time complexity of O(n^2) in the worst and average cases, making it inefficient for large datasets. It requires multiple comparisons and shifts for each element, which can be time-consuming.
2. Inefficient for Large Datasets: Due to its time complexity, Insertion Sort is not recommended for sorting large datasets or real-time applications where efficiency is critical.
3. Not Suitable for Randomly Sorted Datasets: Insertion Sort can be inefficient for datasets that are randomly sorted or have elements in reverse order, as it may require many comparisons and shifts to insert an element at its correct position.

Implementation in Code

Here’s a simple implementation of Insertion Sort in Python:

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

Conclusion

Insertion Sort is a simple and effective sorting algorithm that is suitable for small datasets or partially sorted datasets. It has some advantages in terms of simplicity, adaptability, and space complexity, but it may not be the best choice for large datasets or randomly sorted datasets due to its time complexity.