insertSort.md

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

INSERTION SORT ALGO NOTES:

Sources:

• https://medium.com/javascript-algorithms/javascript-algorithms-insertion-sort-59b6b655373c
• https://medium.com/@ariel.salem1989/an-easy-to-use-guide-to-big-o-time-complexity-5dcf4be8a444

An insertion sort algorithm works with one item at a time, and iteratively places each item into the right order in the array. Comparison sorting algorithms only work where a “less-than” relation is defined (e.g. 2 is less than 5, 3 is not less than 1, alpha is less than beta because a comes before b).

Insertion sort runs in O(n²), or quadratic, time in the worst case. This typically isn’t very effective and should not be used for large lists. Because of insertion sort’s low hidden constant value, however, it usually outperforms more advanced algorithms such as quick sort or merge sort on smaller lists

O(N²) — Quadratic Time: Quadratic Time Complexity represents an algorithm whose performance is directly proportional to the squared size of the input data set

Some other benefits of insertion sort are that

• it’s stable A stable sorting algorithm is any algorithm that won’t change the relative order of items in a list that have the same value.

• it sorts your list in-place Because insertion sort sorts your list in-place, it only uses O(1) (constant) space. This is an example of a time-space tradeoff, where you’re sacrificing the speed of your algorithm in order to conserve memory.

• it’s adaptive. Insertion sort is also adaptive, which means that it works well with arrays that are already partially or fully sorted, which reduces it’s run time to O(nk) where each element in the list is no more than k elements away from it’s sorted position.

Insertion sort works by moving from left to right over an input list. You could compare it to the way you would sort a set of cards that you were holding in your hand. You’d scan the set from left to right, grabbing each card as you go and moving it to the position where the card to it’s left would be smaller or equal to the current card’s value. After you move the card furthest to the right, you’ll be left with a set of cards that has been sorted in ascending order.

You can skip the first item (index 0), since any array of size 1 is trivially sorted