quickSort.js

function partition(arr, low, high) {
  let pivot = arr[high];
  let i = low - 1;
  for (let j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      // if the current element is less than or equal to the pivot,
      // increment i and then swap the current element with arr[i]
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  // Now let us swap the elements arr[i+1] and pivot (arr[high])
  // to place the pivot in the right place.
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  // returning the pivot's index to the caller to indicate that partition is done
  return i + 1;
}

function quickSort(arr, low, high) {
  if (low >= high) {
    return;
  }
  let pivotIndex = partition(arr, low, high);
  // now that we have the pivot's index,
  // let's recursively go through the sub arrays till all of them are sorted
  quickSort(arr, low, pivotIndex - 1);
  quickSort(arr, pivotIndex + 1, high);
}

// populate the array with random 100k integers
let arr = [];
while (arr.length < 100000) {
  arr.push(~~(Math.random() * 100000));
}
console.log(`starting with array with length ${arr.length}`);

console.time("quickSort");
quickSort(arr, 0, arr.length - 1);
console.timeEnd("quickSort");

console.log(arr);