삽입정렬

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];
function insertionSort(array) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] < array[0]) array.unshift(array.splice(i,1)[0]);
    else {
      for (let j = 1; j < i; j++) {
        if (array[i] > array[j - 1] && array[i] < array[j]) array.splice(j, 0, array.splice(i,1)[0]);
      }
    }
  }
  return array;
}

insertionSort(numbers);

// Space Complexity : O(1)
// Time Complexity(Worst): O(n^2)
// Time Complexity(Nearly Sorted): O(n)