Insertion Sort

Insertion sort is the other iterative sort in this unit, with a while loop inside a for loop.

int[] weights = {38, 12, 45, 27, 30};
for (int next = 1; next < weights.length; next++)
{
    int held = weights[next];
    int spot = next - 1;
    while (spot >= 0 && weights[spot] > held)
    {
        weights[spot + 1] = weights[spot];
        spot--;
    }
    weights[spot + 1] = held;
}

The sorted portion starts as the first element alone, since one value is already in order. Each pass takes the next value, the one at index next, and copies it into held. Then spot walks left through the sorted portion. Each value greater than held is copied one place right, and the walk stops at a value that isn't greater or when no positions are left. Then held goes into the gap.

Before the third pass, the array is 12, 38, 45, 27, and 30, and the pass holds 27. The 45 is greater, so it's copied into index 3, and the 38 is greater, so it's copied into index 2. The 12 isn't greater, so the walk stops with spot at 0, and 27 is written at index 1, giving 12, 27, 38, 45, and 30.

Midway through that pass, the array briefly held 45 twice and then 38 twice. Nothing was lost, since the value each copy wrote over had already been copied right or saved in held.

After pass 1, the sorted portion is 12 and 38, in order with each other. But 38 isn't in its final position: the 27 and the 30, not yet examined, both belong ahead of it. Pass 3 and pass 4 each push it one place right. Selection sort's passes put values where they'll end up. Insertion sort's passes only put each value in order among the values examined so far.

The amount of work depends on the data. An array already in increasing order copies nothing on any pass, because each walk stops at its first comparison.