Idea: Insert each element into its correct position

• Best: O(n) (nearly sorted)
• Worst: O(n²)
• Stable: ✅

When to use

• Small arrays
• Nearly sorted data
• Used internally in Java (TimSort)

public class InsertionSort {
    public static void sort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int key = a[i];
            int j = i - 1;
            while (j >= 0 && a[j] > key) {
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = key;
        }
    }
}

Watch for

• Elements shifting right
• Like sorting cards in hand

Mental model: 🃏 Insert into correct position