Insertion Sort

Definition

A comparison-based sorting algorithm that builds the sorted array one element at a time by inserting each element into its correct position in the sorted portion. Like sorting playing cards in your hand!

---

Big O Complexity

---

When to Use

---

Pros and Cons

---

Implementation

Basic Insertion Sort

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

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

        // Shift elements greater than key to the right
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        // Insert key at correct position
        arr[j + 1] = key;
    }
}

With Swaps (Less Efficient)

public void insertionSortSwap(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
            // Swap
            int temp = arr[j];
            arr[j] = arr[j - 1];
            arr[j - 1] = temp;
        }
    }
}

Binary Insertion Sort

// Use binary search to find insertion point
// Reduces comparisons from O(n²) to O(n log n)
// But still O(n²) shifts
public void binaryInsertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];

        // Binary search for insertion position
        int insertPos = binarySearch(arr, 0, i - 1, key);

        // Shift elements right
        for (int j = i - 1; j >= insertPos; j--) {
            arr[j + 1] = arr[j];
        }
        arr[insertPos] = key;
    }
}

private int binarySearch(int[] arr, int low, int high, int key) {
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == key) return mid + 1;
        if (arr[mid] < key) low = mid + 1;
        else high = mid - 1;
    }
    return low;
}

Recursive Insertion Sort

public void insertionSortRecursive(int[] arr, int n) {
    if (n <= 1) return;

    // Sort first n-1 elements
    insertionSortRecursive(arr, n - 1);

    // Insert nth element into sorted portion
    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;
}

Descending Order

public void insertionSortDescending(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] < key) {  // Changed comparison
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Generic Insertion Sort

public <T extends Comparable<T>> void insertionSort(T[] arr) {
    for (int i = 1; i < arr.length; i++) {
        T key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j].compareTo(key) > 0) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

---

Step-by-Step Example

---

Variations

Insertion Sort for Linked List

public ListNode insertionSortList(ListNode head) {
    if (head == null) return null;

    ListNode dummy = new ListNode(0);  // Sorted list
    ListNode curr = head;

    while (curr != null) {
        ListNode next = curr.next;

        // Find insertion position in sorted list
        ListNode prev = dummy;
        while (prev.next != null && prev.next.val < curr.val) {
            prev = prev.next;
        }

        // Insert curr after prev
        curr.next = prev.next;
        prev.next = curr;

        curr = next;
    }

    return dummy.next;
}

Shell Sort (Generalization of Insertion Sort)

// Uses gaps to reduce number of shifts
public void shellSort(int[] arr) {
    int n = arr.length;

    // Start with large gap, reduce to 1
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // Perform insertion sort for this gap
        for (int i = gap; i < n; i++) {
            int key = arr[i];
            int j = i;

            while (j >= gap && arr[j - gap] > key) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = key;
        }
    }
}

Insertion Sort for Partially Sorted

// When only k elements are out of place
// Time: O(n × k)
public void insertionSortPartial(int[] arr) {
    // Same as basic insertion sort
    // Naturally efficient for nearly sorted arrays
    insertionSort(arr);
}

---

Use in Hybrid Sorts

Hybrid Quick Sort Example

public void hybridSort(int[] arr, int low, int high) {
    while (low < high) {
        // Use insertion sort for small arrays
        if (high - low < 10) {
            insertionSort(arr, low, high);
            break;
        }

        // Otherwise use quicksort partition
        int pivot = partition(arr, low, high);

        // Recurse on smaller partition, iterate on larger
        if (pivot - low < high - pivot) {
            hybridSort(arr, low, pivot - 1);
            low = pivot + 1;
        } else {
            hybridSort(arr, pivot + 1, high);
            high = pivot - 1;
        }
    }
}

private void insertionSort(int[] arr, int low, int high) {
    for (int i = low + 1; i <= high; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= low && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

---

Tips & Tricks

---