Implement Quick Sort

Quick sort is an efficient, recursive, divide-and-conquer approach to sorting an array. In this method, a pivot value is chosen in the general array, the array is partitioned into two subarrays of values less than and greater than the pivot. We combine the result of recursively calling the quick sort algo on both subarrays.

• Quick sort’s worst case is O(n²) but that can be avoided if we pick a random pivot point, so that way it’s big O is O(nlogn).

• Its space complexity is O(logn).

function quickSort(array) {
  let n = array.length;
  if(n === 0){
    return [];
  }else{
  let pivot = array[n -1];
  let int_above = [];
  let int_below = [];
  let int_equal = [];
   for(let i of array){
     if(i < pivot){
       int_below.push(i);
     }
     else if(i > pivot){
       int_above.push(i);
     }else{
       int_equal.push(i);
     }
   }
  // Only change code below this line
  return [...quickSort(int_below), ...int_equal, ...quickSort(int_above)];
  // Only change code above this line
  }


}