Insertion sort

In most cases the insertion sort is the best of the elementary sorts described in this chapter.

It still executes in O(N2) time, but it’s about twice as fast as the bubble sort and somewhat faster than the selection sort in normal situations. It’s also not too
complex, although it’s slightly more involved than the bubble and selection sorts. It’s often used as the final stage of more sophisticated sorts, such as quicksort.

The code


var insertion = (function () {
function insertion() {
}
insertion.prototype.sort = function (arr) {
var n = arr.length;
for (var i = 1; i < n; ++i) {
var key = arr[i];
var j = i - 1;
while ((j >= 0 && arr[j] > key)) {
arr[j + 1] = arr[j];
j = j - 1;
}
;
arr[j + 1] = key;
}
;
};
return insertion;
}());



Explanation

In the sort function we loop on an array and on the while loop we replace the element that is before arr[i] but also higher than arr[i] with the current element  arr[j+1]

So if  we have an array [1, 2, 4, 6, 3]  and comment out the last line from our code (arr[j+1] =key) the output will be [1, 2, 4, 4,6].

The last line gives to the first 4 the value from the array that is 3.

(Updated simpler code)



var arr = [1, 3, 2, 5, 100, 23, 54, 123];


for (var i = 0; i < arr.length; i++) {
var temp;
if (arr[i - 1] > arr[i]) {
temp = arr[i];
arr[i] = arr[i - 1]
arr[i - 1] = temp;
}

return arr
}