DEV Community

Dumb Down Demistifying Dev
Dumb Down Demistifying Dev

Posted on • Updated on

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;
    }
Enter fullscreen mode Exit fullscreen mode

Discussion (0)