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;
    }