Insertion Sort Introduction

The Insertion Sort works the way many people sort a poker or a rummy hand. We start with an empty left hand and the cards face down on the table. We then remove one card at a time from the table and insert it into the correct position in the left hand. To find the correct position for a card, we compare it with each of the cards already in the hand, from right to left.

for (i = 2 to n)
    j = i - 1;
    while (j > 0 AND a[j] > a[i])
        swap(j + 1, j);
        j--;

The inner loop of this algorithm is moving the element (card) that is now being inserted from its original position towards the left side into the right slot by comparing the value of every element in the array to the value of the element (card) being processed. The outer loop is keeping track of which element of the arrray is to be inserted into the correct slot and moves to the right.

The i and j variables are colored to match their colors in the animation. You will see the values these variables take
on near the top of the animation.