# Implementation of insertion sort in JavaScript

I have written an insertion sort algorithm in JavaScript:

function insertionSort(inputArray){
var totalElements = inputArray.length - 1;
var temp = 0;
var lastIndex = 0;
var prevIndex = 0;
for(var i = 0; i <= totalElements; i++){
for(var currentIndex = i; currentIndex > lastIndex; currentIndex--){
prevIndex = currentIndex - 1;
if(inputArray[currentIndex] < inputArray[prevIndex]){
temp = inputArray[currentIndex];
inputArray[currentIndex] = inputArray[prevIndex];
inputArray[prevIndex] = temp;
}else{
break;
}
}

}

return inputArray;
}

console.log(insertionSort([1,31,26,4,3,12]));
console.log(insertionSort([5,6,1,2,3,4]));


The output is also proper:

rahul@rahul:~/myPractise/Algo$node sorting.js [ 1, 3, 4, 12, 26, 31 ] [ 1, 2, 3, 4, 5, 6 ] rahul@rahul:~/myPractise/Algo$


Can this be further improved?

Your function can only sort numbers and strings

The built in Array.sort function offers an optional compare function as a parameter. Adding this feature to your insertionSort function would allow for users to sort any type of object:

function defaultCompare(x, y) {
if (x < y)
return -1;
else if (x > y)
return 1;
else
return 0;
}

function insertionSort(array, compare) {
compare = compare ? compare : defaultCompare;
//...
}


You have quite a few variables that aren't necessary

totalElements

You only use this variable once, in the condition of your first for loop. JavaScript has some incredibly fast engines and with JIT-Compiler (just in time compiler) you don't have to worry about micromanaging optimizations like what if js isn't smart enough to know that it's recalculating inputArray.length - 1 each iteration. Defining totalElements arguably makes your code harder to read by adding another variable the scope, and the JS engines are smart-enough/fast-enough that performance isn't likely affected, so I would recommend getting rid of it.

temp

You could eliminate temp by abstracting out a function to swap indices in an array:

function swapIndices(array, index1, index2) {
var temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}


This also improves your code's cohesiveness by abstracting out the technicalities of swapping variables, and it allows you to use swapIndices elsewhere in your code.

lastIndex

This one is just a constant for zero. At the very least you should change the var to const:

const lastIndex = 0;


But I'd recommend to just get rid of it.

prevIndex

I find currentIndex - 1 more clear than prevIndex. The former is obviously the index 1 less than currentIndex whereas the latter could also mean the previously swapped element (precedingIndex is another possible name).

Summary

With all the above changes your code would look like:

function defaultCompare(x, y) {
if (x < y)
return -1;
else if (x > y)
return 1;
else
return 0;
}

function swapIndices(array, index1, index2) {
var temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}

function insertionSort(array, compare) {
compare = compare ? compare : defaultCompare;

for (let i = 0; i < array.length; i++) {
for (let currIndex = i; currIndex > 0; currIndex--) {
if (compare(array[currIndex], array[currIndex - 1]) < 0) {
swapIndices(array, currIndex, currIndex - 1);
}
else {
break;
}
}
}

return array;
}


After reading and running your code, I thought I could make your life easier by turning this pseudocode at Insertion Sort to javascript.

   function insertionSort(inputArray){
var holePosition
var valueToInsert

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

/* select value to be inserted */
valueToInsert = inputArray[i]
holePosition = i

/* Notice I used the while as opposed to the for*/
while ( holePosition > 0 && inputArray[holePosition-1] > valueToInsert){
inputArray[holePosition] = inputArray[holePosition-1]
holePosition = holePosition -1

}
/* insert the number at hole position */
inputArray[holePosition] = valueToInsert
}
return inputArray;
}
var result =insertionSort([1,31,26,4,3,12]);
alert('['+ result.join() + ']');

Note:

• So many variables were defined totalElements, temp, lastIndex and prevIndex which were unnecessary. In the code below, I utilised two variables called holePosition and valueToInsert to serve as Positions for insertion and the values to include in those positions
• I have also replaced your second for statement with a while loop. I would use while loop with a continuous sorting as opposed to a for loop