Insertion Sort is one of the algorithms using which we can sort elements of an array, which could eventually help in searching an element using search algorithms. Most of the resources that speak of Insertion Sort give similar examples of inserting each element of an unsorted array into a sorted one and hence the name of the algorithm is derived from the same concept.

One of the popular examples mentioned is a Cards game. In this game, the dealer would keep giving you a random card and you keep inserting it in ascending order to make it a sorted set. In the same way, we got to check every element from index 1 onwards with the left side Subset. Then move the right side subset to make space for the element in the sorted subset(left side subset). This way we continue to loop until the end of the array and finally achieve a sorted array. When I read this for the first time, I felt how in the world is it possible to shift a subset to create a place for a new element in the subset.

Let me give you another example, say a math teacher is arranging her student's test papers in alphabetical order. She first picks up a paper from the whole set, then picks up another one and checks for its place in hand, and arranges accordingly. then picks another one to check for its place in hand and arranges accordingly. This continues until all the papers are arranged properly.

The thing is these examples showcase the possibility of creating space for a new element in the sorted array, to maintain it in order. However, logically when we apply this for arrays, we are supposed to be swapping elements in order to make place for the new element. Let us understand this better by breaking this algorithm into smaller tasks:

1. Consider the first element to be the sorted array. array[0];
2. Starting from the second element in the array, array[1], we can start passing this to the sorted array to continue.
3. Here, we gonna compare each element in the sorted array with the new element that came from the unsorted array, and accordingly swap if the new one is smaller.
4. This way we sort all the elements from the unsorted array :)

Let us see how can we achieve this:

var insertionSort = function(array) {
 var currentIndexInSortedSubset = 0;
 var currentIndexInUnsortedSubset = 1;
 for(var i=currentIndexInUnsortedSubset; i<= array.length; i++){ //loop for unsorted subset
     for(var j=currentIndexInSortedSubset; j <= i; j++){ //loop for sorted subset
         var temp = array[j];
         if(array[j] > array[i]){
             array[j] = array[i];
             array[i] = temp;
         }
     }
 }
};

var array = [4, 9, 8, 2, 0, 4, 1, 11, 10, 0];
insertionSort(array);
println("Array after sorting:  " + array);

In this algorithm, we are almost running the loop for almost n number of times, considering n as the length of the array. Unless we find the element in the right place every go, that means it is already a sorted array in reverse order, then the time complexity is simple O(1). This is a best-case scenario. And as we are running two for loops here, which makes a possible use case of running each loop to maximum times, the time complexity for the worst-case scenario is O(n*n), i.e; Order of n square.

Thank you for reading so far. I hope this was helpful. Happy learning !!