Quicksort algorithm compare

Question

Can't understand why my sorting algorithm fall down on array with 50000 numbers

const myquicksort2 = (sortedArray) => {

    const sort = (start, end) => {
        if (end - start <= 1) return;
        let pivot = sortedArray[end - 1];
        let pivotIndex = end - 1;

        for (let i = start; i < end; i++) {
            if (sortedArray[i] > pivot && i < pivotIndex) {
                let temp = sortedArray[i];
                sortedArray[i] = pivot;
                sortedArray[pivotIndex] = temp;
                pivot = temp;
            }
        }
        sort(start, pivotIndex);
        sort(pivotIndex + 1, end);
    };

    sort(0, sortedArray.length);

    return sortedArray;
};

I don't create new arrays and change pivot value while sorting, but the second example doesn't fail on 50000 and performs much better on https://jsperf.com/sorting12389

function sort(arr) {
   if (arr.length > 1) {
     const medium = arr[0];
     const leftPart = [];
     const centerPart = [];
     const rightPart = [];

     arr.forEach((item) => {
       if (item < medium) leftPart.push(item);
       if (item > medium) rightPart.push(item);
       if (item === medium) centerPart.push(item);
     })

     return sort(leftPart).concat(centerPart).concat(sort(rightPart));
   } else {
     return arr;
   }
 }

Answer 1

There's a couple issues here.

First, you need to be careful that you are testing correctly with jsperf. Browsers do all sorts of optimizations and if you are sorting the same array over and over again, it's hard to know if you are really testing your sort algorithm. You might consider making a new random array in each test of the loop.

Second, your in-place sort doesn't have a good partition scheme. The beauty of quicksort is that it splits the array into chunks that shrink logarithmically. You are not really doing quicksort here. It's more like bubble sort because your end variable simply counts from array length to zero and with each call you loop over 0 - end of the list. This makes of O(n^2) time. Additionally since pivotIndex is always defined as end - 1, this is a totally wasted recursion:

sort(pivotIndex + 1, end)

To get in-place quicksort to work you need a partition scheme that resets the index of the pivot, then you recuse on start - pivot and pivot+1 - end.

A common partition scheme is Hoare partitioning where you move two variables from opposite sides of the array, swapping as you find values on either side of the pivot. It's not complicated, but easy to screw up the indexes.

The partition is usually written as a separate function, but to keep it close to yours I just inlined it:

const myquicksort2 = (sortedArray) => {
  const sort = (start, end) => {    
      if (end <= start) return;
      let pivot = sortedArray[end];
      let left = start, right = end
     
      // Partion 
      while(left <= right){
        while (sortedArray[left] < pivot){ 
          left++ 
        }     
        while (sortedArray[right] > pivot){ 
          right-- 
        }
        if (left <= right) {
          [sortedArray[left], sortedArray[right]] = [sortedArray[right], sortedArray[left]]
          left++
          right--
        }
      }

      sort(start, right);
      sort(right + 1, end);
  };

  sort(0, sortedArray.length-1);

  return sortedArray;
};

console.log(myquicksort2([5, 7, 2, 1, 11, 10]))

When I run this with time tests in Node, it's considerably faster than the function that makes arrays. In your jsperf, it's not. However, if I make a new array with each loop, it is faster suggesting that there's something we're not seeing in the way jsperf works. Here's an edit of the jsperf

On my laptop with node this sort 100,000 random integers in about 20ms, it take the non-inplace function about 50ms.