Insertion Sort Algorithm with Examples

Insertion Sort is one of the fundamental sorting algorithms that is simple yet powerful. It works similarly to how we arrange playing cards in our hands by inserting each new card into its correct position.

Although it is not the most efficient sorting algorithm, understanding it provides a solid foundation for learning more advanced sorting techniques.

In this guide, we will explore the Insertion Sort algorithm in-depth, understand its step-by-step working, solve practical problems, and discuss real-world applications to help you master this sorting technique.

How Does Insertion Sort Work?

Insertion Sort builds a sorted array one element at a time by comparing the current element with the ones before it and inserting it into its correct position.

Algorithm

Start from the second element (index 1) because we assume the first element is already sorted.
Store the current element (key) and compare it with the elements before it.
Shift all larger elements one position to the right to make space for the key.
Insert the key into its correct position.
Repeat the process for all elements in the array.

Step-by-Step Example

Let’s sort the array:
arr = [5, 3, 8, 6, 2]

Initial Array:

[5, 3, 8, 6, 2]

Pass 1 (i = 1, key = 3)

Compare 3 with 5 → Move 5 to the right
Insert 3 at position 0

Array after Pass 1:

[3, 5, 8, 6, 2]

Pass 2 (i = 2, key = 8)

Compare 8 with 5 → No shifting needed
8 is already in the correct place

Array after Pass 2:

[3, 5, 8, 6, 2]

Pass 3 (i = 3, key = 6)

Compare 6 with 8 → Move 8 to the right
Compare 6 with 5 → No shifting needed
Insert 6 at position 2

Array after Pass 3:

[3, 5, 6, 8, 2]

Pass 4 (i = 4, key = 2)

Compare 2 with 8 → Move 8 to the right
Compare 2 with 6 → Move 6 to the right
Compare 2 with 5 → Move 5 to the right
Compare 2 with 3 → Move 3 to the right
Insert 2 at position 0

Final Sorted Array:

[2, 3, 5, 6, 8]

Python Implementation

Here’s how you can implement Insertion Sort in Python:

def insertion_sort(arr):
    for i in range(1, len(arr)):  # Start from the second element
        key = arr[i]  # Store the current element
        j = i - 1

        # Move elements that are greater than key to one position ahead
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key  # Insert the key at the correct position

arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print("Sorted array:", arr)  # Output: [5, 6, 11, 12, 13]

Time and Space Complexity Analysis

Case	Time Complexity
Best Case (Already Sorted)	O(n)
Worst Case (Reversed Order)	O(n²)
Average Case	O(n²)

Space Complexity: O(1) (since sorting is done in place)

Understand what time complexity is, why it is essential, and how it impacts algorithm efficiency and performance in programming.

Advantages and Disadvantages

Advantages of Insertion Sort Algorithm:

✔️ Simple and easy to implement.
✔️ Efficient for small datasets.
✔️ In-place sorting (no extra memory required).
✔️ Stable sorting algorithm (maintains the order of equal elements).

Disadvantages of Insertion Sort Algorithm:

❌ Inefficient for large datasets due to O(n²) complexity.
❌ Not suitable for real-world applications involving large data.

Applications of Insertion Sort

Sorting Small Data Sets – Efficient for small arrays.
Nearly Sorted Arrays – Runs in O(n) time when the array is nearly sorted.
Online Sorting – Useful when data arrives dynamically and needs sorting in real time.
Hybrid Sorting Algorithms – Used in Timsort and QuickSort for small partitions.
Handling Linked Lists – Works efficiently with linked lists.
Educational Purposes – Used to teach sorting concepts.
Used in Shell Sort – A variation of Insertion Sort that sorts elements at specific intervals.
Used in Computer Graphics – Used for real-time rendering and ordering tasks.

Problem statements and their solutions using insertion sort

Problem 1: Sort an Array Using Insertion Sort

Problem Statement:
Given an array of integers, sort the array in ascending order using the Insertion Sort algorithm.

Python Solution:

def insertion_sort(arr):
    for i in range(1, len(arr)):  # Start from the second element
        key = arr[i]  # Store the current element
        j = i - 1

        # Move elements that are greater than key to one position ahead
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key  # Insert the key at the correct position

arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print("Sorted array:", arr)  # Output: [5, 6, 11, 12, 13]

Problem 2: Sort an Array in Descending Order Using Insertion Sort

Problem Statement:
Modify the Insertion Sort algorithm to sort an array in descending order.

Python Solution:

def insertion_sort_desc(arr):
    for i in range(1, len(arr)):  # Loop through unsorted elements
        key = arr[i]  # Take the current element
        j = i - 1

        # Shift elements that are smaller than key
        while j >= 0 and arr[j] < key:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key  # Place key at the correct position

arr = [4, 7, 2, 9, 1]
insertion_sort_desc(arr)
print("Sorted array in descending order:", arr)  # Output: [9, 7, 4, 2, 1]

Problem 3: Count the Number of Shifts in Insertion Sort

Problem Statement:
Write a function that counts the number of shifts (element moves) required to sort an array using Insertion Sort.

Python Solution:

def count_shifts_insertion_sort(arr):
    shifts = 0  # Initialize shift counter
    for i in range(1, len(arr)):  # Traverse the array
        key = arr[i]  # Take the current element
        j = i - 1
        # Shift elements to make space for key
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
            shifts += 1  # Count each shift
        arr[j + 1] = key  # Place key at the correct position
    return shifts  # Return total shifts count

arr = [8, 4, 3, 7, 2]
print("Number of shifts:", count_shifts_insertion_sort(arr))  # Output: 6

Conclusion

Insertion Sort is a simple yet effective sorting algorithm that works by gradually building a sorted list one element at a time. It is particularly useful for small datasets or nearly sorted arrays due to its O(n) best-case time complexity. However, for larger datasets, Merge Sort or Quick Sort are preferred due to their better average-case performance.

Key Takeaways:

✅ Stable Sorting Algorithm (Preserves the order of duplicate elements)
✅ Efficient for Small/Nearly Sorted Data
✅ Not Suitable for Large Datasets (O(n²) worst-case complexity)
✅ Used in Online Sorting (Real-time data processing)

Frequently Asked Questions

1. Why is Insertion Sort efficient for nearly sorted arrays?

Insertion Sort performs best when the array is almost sorted because fewer shifts are required, leading to an O(n) time complexity, which is much better than its usual O(n²) in worst cases.

2. Can Insertion Sort be implemented recursively?

Yes! Instead of using a loop, we can use recursion to sort the first (n-1) elements and then insert the last element into its correct position.

3. How does Insertion Sort compare to Bubble Sort and Selection Sort?

Insertion Sort is faster than Bubble Sort because it reduces unnecessary swaps.
Selection Sort is better in terms of swaps but still takes O(n²) time.
Among the three, Insertion Sort is preferred for small or nearly sorted arrays.

4. Is Insertion Sort a stable sorting algorithm?

Yes, Insertion Sort is stable because it does not change the relative order of equal elements in the array.

5. Can Insertion Sort be used for large datasets?

Not really. Due to its O(n²) time complexity, it becomes inefficient for large datasets. Merge Sort or Quick Sort are better options for handling large datasets efficiently.