Learn Insertion Sort with Video Game Discs

I think you could say I have an average number of video game discs. It’s not a huge number of games, but it is enough that it can be difficult to find a particular game if they’re not organized in a predictable way.

Enter insertion sort. Insertion sort is in the same family as the bubble sort in that its worst case complexity is O(n2). But in practice, it is usually a faster sort.

So we start with a few game discs that we want to sort. To simplify this demonstration each game is numbered.

The sort begins by comparing the first two discs with each other, and ordering them appropriately. We see that the 4 is moved to before the 27.

At this point, the insertion sort looks remarkably similar to the bubble sort. the interesting part will be shown soon. First we move onto the next game disc. The 42 gets compared to the 27 and stays where it is because it is already in order relative to the 27.

Now comes the interesting part. The 21 is goes before the 42 and before the 27. So our insertion sort technique inserts the 21 into the correct spot.

Then we get to the last game disc. An 8. This gets inserted after the 4 and before the 21.

Now the entire list of game discs has been sorted. We see the process working, but now we need to translate this process into a computer algorithm.

Insertion Sort Example in JavaScript

// set up the array with random values
var sortMe = new Array();
var arrayLength = 5;
var i = 0;
for(; i < arrayLength; i++) {
    sortMe[i] = Math.floor((Math.random()*20)+1);
}

var logText = "";
i = 0;
for(; i < arrayLength; i++) {
    logText += sortMe[i] + ", ";
}
console.log("Starting Values: \t" + logText);

// begin insertion sort
i = 1;
var j, temp, k;

for(; i < arrayLength; i++) {
    temp = sortMe[i];
    j = i;
    while(j > 0 && sortMe[j-1] > temp) {
        sortMe[j] = sortMe[j-1];
        j--;
    }
    sortMe[j] = temp;

    logText = "New Order:\t\t";
    k=0;
    for(; k < arrayLength; k++) {
        logText += sortMe[k] + ", ";
    }
    console.log(logText);
}

Here’s a link to the working example.