Insertion Sort in AP CSA: Shift, Insert, Trace

Insertion sort is the second sorting algorithm on the 2026 AP CSA exam. Unlike selection sort, it shifts elements rather than swapping. Understanding the shift-and-insert pattern is essential for tracing questions and distinguishing it from selection sort.

🔧 How Insertion Sort Works

Think of sorting a hand of playing cards. You pick up each card and slide it into the correct position among the cards you have already sorted.

1. Save: Store the current element in a temporary variable
2. Shift: Move all larger sorted elements one position to the right
3. Insert: Place the saved element into the gap

📋 Complete Trace Example

Sort the array {7, 3, 5, 1, 4} using insertion sort:

Key observation: on pass 3, the value 1 caused THREE shifts. Insertion sort can move many elements in a single pass.

💻 The Code (AP Exam Version)

public static void sort(int[] data)
{
    for (int j = 1; j < data.length; j++)
    {
        int temp = data[j];
        int pos = j;
        while (pos > 0 && data[pos - 1] > temp)
        {
            data[pos] = data[pos - 1];
            pos--;
        }
        data[pos] = temp;
    }
}

⚖ Selection Sort vs Insertion Sort

❌ Common Pitfalls

✏ Practice Questions

for (int j = 1; j < arr.length; j++)
{
    int val = arr[j];
    int k = j;
    while (k > 0 && arr[k - 1] > val)
    {
        arr[k] = arr[k - 1];
        k--;
    }
    arr[k] = val;
}

❓ Frequently Asked Questions