Insertion sort algorithm in javascript

A simple implementation of insertion sort algorithm in javascript.

Insertion sort is one of the simplest and most widely used sorting algorithm.

Just imaging a deck of card in your hands and how will you sort these cards?.

The simple answer is we will pick the smallest card and place it at first position, then second smallest at second position, third smallest at third and so on depending upon the sorting order.

It also sorts the elements by placing the smallest element at first place then second smallest at second place and so on.

Example

Input:
[1, 8, 2, 4, 5]

Output:
//sorted in ascending order
[1, 2, 4, 5, 8]

Check out the following image to have better understanding.

Pseudo Code

for i = 1 to array.length - 1
   key = array[i];
   j = i - 1;
   //Sort in ascending order
   while(j >= 0 && array[j] > key)
      arr[j + 1] = arr[j];
      j = j - 1;

   arr[j + 1] = key;

---

Insertion Sort Implementation in javascript

• We will use two nested loops to sort the elements.
• In the first loop, we will start the loop from the second element as we need to check it with the first element for sorting.
• In the second loop we will iterate all the elements before the current element of the first loop and swap them if it is less than or greater than based on the sorting order.

let insertionSort = (arr, n = arr.length) => {
    for(let i = 1; i < n; i++){
      let key = arr[i];
      let j = i - 1;
        
      //Sort in the ascending order
      while(j >= 0 && arr[j] > key){
        arr[j + 1] = arr[j];
        j = j - 1;
      }
        
      arr[j + 1] = key;
    }
  
  return arr;
}

Input:
console.log(insertionSort([1, 8, 2, 4, 5]));

Output:
[1, 2, 4, 5, 8]

Time Complexity Of Insertion Sort

---

Space Complexity Of Insertion Sort

• Average and Worst case sorting occurs when all or some elements are sorted in reverse order. Best case occurs when all the elements are already sorted.
• Sorting In place: Yes. It does not uses extra space to sort the elements.
• Stable: Yes. It is a stable sorting algorithm.

Uses

Insertion sort is used when we need to sort the less amount of elements, For example chrome’s V8 engine uses Insertion sort in the sort() method if there are less than 20 elements.

It can also be used for large amounts of elements when the elements are almost sorted and only few elements need to be swapped.

Recursive Insertion Sort.

Other Sorting Algorithms

• Bubble Sort
• Recursive Bubble Sort
• Selection Sort