INSERTION SORT - A TRUE LIFE STORY

 Insertion sort is  just how we normally sort list of items. We start from the second item and compare with the first. We swap if it is less than the first else, we do nothing. Thus, in general for each item, we compare it with all items that come before it and insert it where appropriate.
 In a more detailed treatment, the insertion sort algorithm works this way:
 We take each element starting from the second element, store it in a variable and then continue to compare it with all elements to its left. At each comparison, if the element to the left is greater than the element stored in the variable, we move it one step to the right and move one step to the left to make the next comparison. This process continues until when an element that is less than the stored variable is encountered. At that comparison, we simply copy the stored variable to the position just before. With that, we are done with the element stored in the variable and so, proceed to the next element to carry out similar steps. This continues until the array is fully sorted.

Pseudocode for Insertion Sort:
 Here is the algorithm for insertion sort that sorts an array of elements A, in increasing order.

InsertionSort (A)
for ( i=0 to A.length){
   j=i
  v = A[i]
  while(A[j-1] > v){
      A[j] = A[j-1]
      j = j - 1
  }
  A[j] = v
}
   

JavaScript Implementation of Insertion Sort:

function insertionSort (A){
for ( i=0; i< A.length; i++){
   j=i;
  v = A[i];
  while(A[j-1] > v){
      A[j] = A[j-1];
      j = j - 1;
  }
  A[j] = v;
}
console.log(A);
}
var A = [6,5,4,3,2,1];
insertionSort(A);