Insertion Sort

function sort (arr) {
    const len = arr.length;

    for (let i = 1; i < len; i++) {
        const 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;
}

How it works

1. grab an item from a set
2. insert it in the result array
3. grab a new item from the set
4. find where it fits in the result array
5. insert it there
6. repeat steps 3-5 until no more items in the original set

Info

• simple to implement algorithm
• builds the resulting sorted array one item at a time
• efficiency/speed
  • slower than quick/heap/merge sort
  • faster than selection/bubble sort
  • caveat:
    • fast on very small arrays
      • faster than quicksort
        • good quicksort implementations will default to insertion sort when the array is under a certain threshold
    • fast on already sorted arrays
      • not all sorting algorithms are
  • best case O(n)
  • worst case O(n^2)
  • average case O(n^2)
• memory
  • O(1)
  • only requires a constant amount of memory
• is a quadratic sorting algorithm
  • whatever that means
• stable
  • this means that it doesn’t change the order of elements with equal keys
• online
  • means it can sort one at a time, rather than needing the whole set up front
• can be done in place by just keeping track of which part of the array is already sorted (assuming a mutable array)