Insertion Sort

What do we understand about Insertion Sort?

• It uses 2 loops (outer for-loop & inner while-loop) and 2 pointers
• 1st pointer starts from 1 item after the 2nd pointer
• 2nd pointer starts from 1 item before 1st pointer
• 2nd loop loops decrementally till 0
• as long as current value is more than left side value we copy the left side over to current
• insertion happens after the 2nd loop is finished
• Mutation is performed on the original Array
• Time complexity
  • Best -> O(n)
  • Average -> O(n^2)
  • Worst -> O(n^2)
• Space complexity
  • O(1)

 function InsertionSort(arr) { for (let i = 1; i < arr.length ; i++) { let currentValue = arr[i]; let oneIndexBefore = i - 1; while (oneIndexBefore >= 0 && arr[oneIndexBefore] > currentValue) { arr[oneIndexBefore + 1] = arr[oneIndexBefore]; oneIndexBefore--; } arr[oneIndexBefore + 1] = currentValue; } return arr; }