An implementation of insertion sort

insertion-sort.js

// Average case O(n^2)
function insertionSort (arr) {
  // Begin at position 1, because we need to compare the element at
  // that position to the previous element
  for (let i = 1; i < arr.length; i++) {
    let j = i

    // If the prior element is greater than the current element (arr[j]), swap
    while (j > 0 && arr[j-1] > arr[j]) {
      // Storing the tmp variable requires O(1) memory space
      let tmp = arr[j]

      arr[j] = arr[j-1]
      arr[j-1] = tmp

      j--
    }
  }
  return arr
}