Insertion Sort

What is Insertion Sort?

Insertion sort builds the sorted array one element at a time. It picks each element and inserts it into its correct position in the already-sorted portion, shifting larger elements right to make room. Think of how you sort playing cards in your hand.

Case	Time	Space	Stable?
Best	O(n) â€” already sorted	O(1)	Yes
Average	O(nÂ²)	O(1)	Yes
Worst	O(nÂ²) â€” reverse sorted	O(1)	Yes

How it Works

For array [12, 11, 13, 5, 6]:

i=1: key=11. 12 > 11 â†’ shift 12 right â†’ insert 11 â†’ [11, 12, 13, 5, 6]
i=2: key=13. 12 < 13 â†’ no shift â†’ [11, 12, 13, 5, 6]
i=3: key=5. 13,12,11 > 5 â†’ shift all â†’ insert 5 â†’ [5, 11, 12, 13, 6]
i=4: key=6. 13,12,11 > 6 â†’ shift â†’ insert 6 â†’ [5, 6, 11, 12, 13] âœ“

Insertion Sort Implementation

import java.util.Arrays;

public class InsertionSort {

    static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];  // element to be inserted
            int j = i - 1;

            // Shift elements greater than key one position right
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;  // insert key at correct position
        }
    }

    // Recursive insertion sort
    static void insertionSortRec(int[] arr, int n) {
        if (n <= 1) return;
        insertionSortRec(arr, n - 1);  // sort first n-1 elements
        int key = arr[n - 1];
        int j = n - 2;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        System.out.println("Before: " + Arrays.toString(arr));
        insertionSort(arr);
        System.out.println("After:  " + Arrays.toString(arr));
        // After: [5, 6, 11, 12, 13]

        // Best case: already sorted â€” O(n)
        int[] sorted = {1, 2, 3, 4, 5};
        insertionSort(sorted);
        System.out.println("Sorted: " + Arrays.toString(sorted));
    }
}

/*
 * Insertion sort is excellent for:
 * - Small arrays (n < 20) â€” low overhead
 * - Nearly sorted data â€” O(n) in best case
 * - Online sorting â€” can sort as data arrives
 * - Used as a subroutine in Timsort (Python/Java's built-in sort)
 */

Step-by-Step Trace