How does the logic actually work in practice?

Think of Insertion Sort like sorting a hand of playing cards. You start with an empty left hand and the cards face down on the table. You pick up one card at a time and slide it into the correct position in your left hand. By the time you've picked up the last card, the hand is sorted.

In C, we do this by treating the first element of the array as a "sorted" list of one. We then look at the second element (the "key") and compare it to the first. If it's smaller, we shift the first element to the right and drop the key into the first slot. We repeat this for every element in the array. I find this much more intuitive than Bubble Sort because it mimics how humans actually organize things.

// A quick glimpse at the outer loop structure
for (int i = 1; i < n; i++) {
    int key = arr[i];
    int j = i - 1;

    // This is where the "sliding" happens
    while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j = j - 1;
    }
    arr[j + 1] = key;
}

Why do I need a temporary 'key' variable?

You might be tempted to just use a series of swaps, but that's inefficient. A swap takes three assignments. By using a key variable, we "pluck" the value out of the array, leaving a conceptual hole. Instead of swapping, we simply shift elements to the right until we find the spot where the key belongs.

If we didn't save arr[i] into key, the first time we performed arr[j + 1] = arr[j], we would overwrite the value we were trying to sort. I've seen a lot of students forget this and spend an hour wondering why their array suddenly ends up full of duplicate numbers. Always grab your key first.

How do I avoid crashing when the key is the smallest element?

This is where most C programmers trip up: the boundary condition. Look closely at the while loop: while (j >= 0 && arr[j] > key).

The order of those conditions is critical. In C, the && operator short-circuits. If j >= 0 is false, the computer won't even look at arr[j]. If you flipped them and wrote while (arr[j] > key && j >= 0), the program would try to access arr[-1] the moment the key was the smallest value in the set. That's a guaranteed segmentation fault or, worse, a silent memory corruption that makes your program behave randomly.

Also, notice that we place the key at arr[j + 1] after the loop. Since the loop ends when j is one position to the left of where the key should go, adding one puts it exactly where it needs to be.

📋 Practical Task

Build a High-Score Leaderboard Sorter

You've been tasked with creating a leaderboard for a retro arcade game. You have an array of 10 unsorted integers representing player scores. Write a program that implements the Insertion Sort algorithm to sort these scores in descending order (highest score first) rather than the standard ascending order.

• Create an array with these values: {450, 1200, 800, 300, 2100, 150, 900, 1100, 700, 600}.
• Modify the while loop condition so that the larger numbers move to the front.
• Print the final sorted array to the console.