Why is my call stack size exceeded during this quicksort?

Question

What is going wrong when i am trying to implement quicksort in JS ? I am getting a call stack size exceeded error.

function quicksort(arr) {
  if (arr.length <= 1)
    return arr;
  let pivot = Math.floor(arr.length / 2);
  const left = [], right = [];
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    }
    else {
      right.push(arr[i]);
    }
  }
  return quicksort(left).concat(pivot, quicksort(right));
}

console.log(quicksort([2, 5, 9, 5, 67, 1, 23, 9]));

Answer 1

When your code builds the left and right arrays, that process includes the pivot value. Thus the total length of those two sub-arrays is the same as the overall length of the original array.

If you skip the pivot element, then the sort works (at least for your test case):

function quicksort(arr) {
  if (arr.length <= 1)
    return arr;
  let pp = Math.floor(arr.length / 2), pivot = arr[pp];
  const left = [], right = [];
  for (var i = 0; i < arr.length; i++) {
    if (i == pp) continue;
    if (arr[i] < pivot) {
      left.push(arr[i]);
    }
    else {
      right.push(arr[i]);
    }
  }
  return quicksort(left).concat(pivot, quicksort(right));
}

console.log(quicksort([2, 5, 9, 5, 67, 1, 23, 9]));

As I noted in a comment above, one of the key features of quicksort among other good sorting algorithms is that it can be done with a constant space overhead. Real implementations do not create new sub-arrays. Instead, they rearrange elements in the original array. The recursion step includes start and end indexes instead of complete new arrays.