Insertion Sort Algorithm

Insertion Sort builds the final sorted array one item at a time. It is much like sorting playing cards in your hands:

• Start with an empty (or one-element) sorted part.
• Pick the next element from the unsorted part.
• Insert it into the correct position in the sorted part by shifting larger elements to the right.

Time Complexity

• Best case: O(n) → already sorted
• Average and Worst case: O(n²)
• Space Complexity: O(1) → In-place sort

It’s efficient for small or nearly sorted datasets.

Code Example

public class InsertionSortExample {

    public static void insertionSort(int[] arr) {
        int n = arr.length;

        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;

            // Shift elements of arr[0..i-1] that are greater than key
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }

            arr[j + 1] = key;

            // Print the array after each insertion
            printArray(arr);
        }
    }

    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        System.out.println("Original array:");
        printArray(arr);

        System.out.println("\nSorting steps:");
        insertionSort(arr);

        System.out.println("\nSorted array:");
        printArray(arr);
    }
}

Output

Original array:
12 11 13 5 6 

Sorting steps:
11 12 13 5 6 
11 12 13 5 6 
5 11 12 13 6 
5 6 11 12 13 

Sorted array:
5 6 11 12 13 

Visual Explanation (Step-by-Step)

Initial Array:

[12, 11, 13, 5, 6]

🔁 Pass 1: i = 1, key = 11

Compare with 12 → shift 12 to the right → insert 11 before it

[11, 12, 13, 5, 6]

🔁 Pass 2: i = 2, key = 13

13 > 12 → no shifting needed

[11, 12, 13, 5, 6]

🔁 Pass 3: i = 3, key = 5

5 < 13 → shift 13
5 < 12 → shift 12
5 < 11 → shift 11
Insert 5 at position 0

[5, 11, 12, 13, 6]

🔁 Pass 4: i = 4, key = 6

6 < 13 → shift 13
6 < 12 → shift 12
6 < 11 → shift 11
Insert 6 at position 1

[5, 6, 11, 12, 13]

✅ Final Sorted Array:

[5, 6, 11, 12, 13]