What is Insertion Sort?

Insertion Sort is a comparison-based algorithm that builds the sorted array one element at a time. It works similarly to how you would sort a hand of cards. You take one element from the unsorted portion of the array and place it in the correct position in the sorted portion.

How Insertion Sort Works:

Start with the second element of the array (assuming the first element is already "sorted").
Compare the current element with the elements in the sorted portion.
Shift elements in the sorted portion to the right if they are greater than the current element.
Insert the current element into its correct position.
Repeat the process for all remaining elements until the entire array is sorted.

Step-by-Step Example:

Consider the array:
[12, 11, 13, 5, 6]

First Iteration:
Start with the second element 11.
- Compare 11 with 12: Swap → [11, 12, 13, 5, 6]
Second Iteration:
Move to 13.
- No swaps are needed since 13 is already in the correct position.
Third Iteration:
Move to 5.
- Compare 5 with 13: Shift → [11, 12, 13, 13, 6]
- Compare 5 with 12: Shift → [11, 12, 12, 13, 6]
- Compare 5 with 11: Shift → [11, 11, 12, 13, 6]
- Place 5 in the correct position: [5, 11, 12, 13, 6]
Fourth Iteration:
Move to 6.
- Compare 6 with 13: Shift → [5, 11, 12, 13, 13]
- Compare 6 with 12: Shift → [5, 11, 12, 12, 13]
- Compare 6 with 11: Shift → [5, 11, 11, 12, 13]
- Place 6 in the correct position: [5, 6, 11, 12, 13]

Now the array is sorted as [5, 6, 11, 12, 13].

Insertion Sort in Java:

Here’s a Java implementation of the Insertion Sort algorithm:

import java.util.Arrays;

public class InsertionSort {
    public static void swap(int nums[], int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void insertionSort(int nums[]) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int j = i;
            while (j > 0 && nums[j - 1] > nums[j]) {
                swap(nums, j, j - 1);
                j--;
            }
        }
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        int nums[] = { 13, 5, 24, 55, 107, 2, 89, 8 };
        insertionSort(nums);
        System.out.println(Arrays.toString(nums));

    }

}

Time Complexity of Insertion Sort:

Best Case Time Complexity:
- O(n) when the array is already sorted. In this case, no shifting is required, and the algorithm only makes one comparison per element.
Average and Worst Case Time Complexity:
- O(n²). In the worst case (when the array is sorted in reverse order), each element needs to be compared with and shifted past all the previously sorted elements.
Space Complexity:
- O(1) because Insertion Sort is an in-place algorithm, meaning it requires only a constant amount of additional memory.

Advantages and Disadvantages:

Advantages:

Simple to implement and understand.
Works efficiently on small or nearly sorted arrays.
It is a stable algorithm, meaning the relative order of equal elements is preserved.
Performs well on small datasets or when the list is nearly sorted.

Disadvantages:

Inefficient for large datasets due to its O(n²) time complexity.
Slower compared to more advanced algorithms like Quick Sort or Merge Sort.

Optimization for Insertion Sort:

One optimization is to use binary search to find the correct position of the element to insert, reducing the number of comparisons. However, this doesn’t improve the overall time complexity since shifting elements still requires O(n) operations.

Mastering Insertion Sort: A Step-by-Step Guide

Table of contents