Data Structures and Algorithms Show(3): Insertion Sort

Insertion Sort gets its name because every element in the array try to find a position closer to the start position of the array. The movement is just like a insertion action. The sort process start from the second element in the array. if the element is smaller than those elements before it, then those elements will be shifted toward its position. As a result, this element can be inserted to the place which is empty after the shift. The sort process completes when the last element in the array go through the steps.

With the first glance, it may look like this sort algorithm that is better than Bubble Sort but worse than Selection Sort. Surprise enough, Insertion Sort is even a little bit better than Selection Sort.

Any way, we need to know that all these three sort algorithms are not using by most of the programs in our computer because they are not efficient enough. They all need two layers loops to compare and move elements. In the worse scenario, an array with n elements may need n*n times steps to achieve the result. It could be 1 million if n is 1000.

for (var i = 1; i < list.length; i++) {

var select = list[i];

var insPos = i;

for (var j = i - 1; j >= 0; j--) {

if (select < list[j]) {

list[j + 1] = list[j];

insPos = j;

}else{

break;

}

}

list[insPos] = select;

}