insertionSort

[phymo]

function bubbleSort(originalArray) {
  let arr = [...originalArray];
  let len = arr.length;
  let flag = false;

  // average case: O(n^2)
  // worst case: O(n^2)
  for (let i = 0; i < len; i++) {
    flag = false;
    for (let j = 0; j < len - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        flag = true;
      }
    }
    // if no swap, then break
    // best case: O(n)
    if (!flag) {
      break;
    }
  }
  return arr;
}

let arr1 = [2, 4, 1, 3, 5];
let arr2 = [2, 4, 1, 3, 5, 6, 6, 7, 7, 8, 9, 10, 0, -5];

console.log(bubbleSort(arr2));