InsertionSort.js

/* In insertion sort, we divide the initial unsorted array into two parts;
* sorted part and unsorted part. Initially the sorted part just has one
* element (Array of only 1 element is a sorted array). We then pick up
* element one by one from unsorted part; insert into the sorted part at
* the correct position and expand sorted part one element at a time.
*/
export function insertionSort (unsortedList) {
  const len = unsortedList.length
  for (let i = 1; i < len; i++) {
    let j
    const tmp = unsortedList[i] // Copy of the current element.
    /* Check through the sorted part and compare with the number in tmp. If large, shift the number */
    for (j = i - 1; j >= 0 && (unsortedList[j] > tmp); j--) {
      // Shift the number
      unsortedList[j + 1] = unsortedList[j]
    }
    // Insert the copied number at the correct position
    // in sorted part.
    unsortedList[j + 1] = tmp
  }
}