Implementation of insertion sort algorithm in Javascript

Insertion-sort is one of the most common sorting algorithms used by computer programmers to sort their data. It takes an input which is a sequence of n finite set of numbers , then a permutation (reordering) is applied to the sequence, such that the element with index[n] in the sequence is less or equal to the element with index[n+1] or vise versa .

The numbers we wish to sort are called keys(elements), due to the fact that the inputs are a sequence, the n numbers are going to come to us in a form of an array. before i propose to you a pseudo code and its implementation, i will introduce an analogy of sorting a hand of cards to better illustrate how the algorithm works.

lets say you have 5cards all are face-down, you pick the first card and you turn it face up, then you have to pick another card and turn it face up (insertion) so that you have a degree of comparison (2-cards), you iterate the process till all cards are face up and sorted.

Lets consider the following pseudo code from chapter 2 of the book titled introduction to algorithms by Cormen et al

for j = 2 to A.length
   key= A[j]
   i= j-1
   while i>0 and A[i]> key
    A[i+1]=A[i]
    i=i-1
A=[i+1] = key

The design approach used for its implementation in javascript is an incremental approach, and it looks something like this.

var A = [3,1,9,5,4];
for (let index = 0; index < A.length; index++) {
const key = A[index]
let i = index -1;
while (i >= 0 & A[i]> key) {
A[i+1] = A[i]
i = i-1;
A[i+1] = key
}
// console.log(key);
}
console.log(A);
//Sort Ascending

To sort in descending order you only need to change the A[i]>key comparison sign to <. It is of paramount to note that the following code does the same as the above code.

var A = [3,1,9,5,4];
A.sort(function(a,b){
return a-b;
})
console.log(A)

If you would like me to share more information with you, you can direct message me on twitter .