1
var sortArray = function (nums) {
2
  return quickSort(nums, 0, nums.length - 1);
3
};
4

5
const quickSort = (arr, start, end) => {
6
  // base case
7
  if (start >= end) return arr;
8

9
  // return pivot index to divide array into 2 sub-arrays.
10
  const pivotIdx = partition(arr, start, end);
11
  // sort sub-array to the left and right of pivot index.
12
  quickSort(arr, start, pivotIdx - 1);
13
  quickSort(arr, pivotIdx + 1, end);
14

15
  return arr;
16
};
17

18
const partition = (arr, start, end) => {
19
  // select a random pivot index, and swap pivot value with end value.
20
  const pivotIdx = Math.floor(Math.random() * (end - start + 1)) + start;
21
  [arr[pivotIdx], arr[end]] = [arr[end], arr[pivotIdx]];
22

23
  const pivotVal = arr[end];
24
  // loop from start to before end index (because pivot is stored at end index).
25
  for (let i = start; i < end; i++) {
26
    if (arr[i] < pivotVal) {
27
      // swap smaller-than-pivot value (at i) with the value at the start index.
28
      // This ensures all values to the left of start index will be less than pivot.
29
      [arr[i], arr[start]] = [arr[start], arr[i]];
30
      start++;
31
    }
32
  }
33

34
  // swap pivot (which was stored at end index) with value at start index.
35
  // This puts the pivot in its correct place.
36
  [arr[start], arr[end]] = [arr[end], arr[start]];
37
  return start;
38
};
39

40
/*
41
Note: Instead of always picking a fixed index as the pivot (ie. start or end index),
42
The pivot was randomly selected to mitigate the odds of achieving worst case TC and SC.
43
TC:
44
Best and avg case: O(nlogn)
45
worst case: O(n^2)
46

47
SC:
48
Since algo done in-place, space comes from recursive call stack.
49
best and avg case: O(logn)
50
worst case: O(n)
51
*/