Is there something wrong with this quicksort implementation that uses a random pivot?

Question

  const swap = (arr, i, j) => {
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  };

  const partition = (arr, left, right) => {
    const pivot = arr[Math.floor(Math.random() * (arr.length - left) + left)];
    while (left <= right) {
      while (arr[left] < pivot) {
        left++;
      }
      while (arr[right] > pivot) {
        right--;
      }
      if (left <= right) {
        swap(arr, left, right);
        left++;
        right--;
      }
    }
    return left;
  };

  const quickSort = (arr, left, right) => {
    if (left === undefined) {
      left = 0;
      right = arr.length - 1;
    }
    if (left >= right) {
      return arr;
    }
    const pIndex = partition(arr, left, right);
    quickSort(arr, left, pIndex - 1);
    quickSort(arr, pIndex, right);
    return arr;
  };

I'm always getting the right results, but I used a tool to check the time it takes to run, and it varies drastically for large inputs. I imagine it has to do with the random pivot, but I'm still not convinced that's it. I'm kind of new to sorting algorithms and I've been analyzing the code in a debugger for awhile, but I'm not sure that there isn't a mistake or inaccuracy somewhere. I'd appreciate if someone can look it over and verify whether or not this algorithm is implemented correctly. Let's assume for now that I want to maintain the random pivot over picking the middle element, or some other way.

Answer 1

Yes, your choice of the pivot is broken. You're choosing an element anywhere from left to the end of the array, not an element between left and right.