quickSort

[phymo]

function quickSort(originalArray) {

  let arr = [...originalArray];
  let len = arr.length;
  if(len <= 1) {
    return arr;
  }
  let pivot = arr.shift();
  len = arr.length;
  let left = [];
  let right = [];

  // average case: O(n log n)
  // best case: O(n log n)
  // worst case: O(n^2)
  while(len) {
    if (arr[len-1] < pivot) {
      left.push(arr[len-1]);
    }
    else {
      right.push(arr[len-1]);
    }
    len--;
  }
  return [...quickSort(left), pivot, ...quickSort(right)];
}

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

console.log(quickSort(arr2));