Insertion Sort

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

Explanation: Insertion sort builds the sorted array one element at a time.

⏱ O(n²) | 💾 O(1)