Infinite recursion in JavaScript quicksort?

Question

Here is the quicksort code I wrote. The function doesn't work because it can't reach the base case. If I log the pivot, r and l to the console, they remain the same no matter how many times the sort function is called. So I wonder if the argument l, r are not really passed into the function as data. Why did it happen?

function sort(data){     if(data.length < 2){         return data;     }     else{         var l = [];         var r = [];         var pivot = parseInt(data.length/2);         for(i=0; i<data.length; i++){             if(data[i] > data[pivot]){                 r.push(data[i]);             }             else{                 l.push(data[i]);             }         }         return sort(l).concat(sort(r));     } } 

Answer 1

I think that the issue here is that your partitioning step does not necessarily shrink the input array. For example, let's trace what happens if you try sorting [1, 2]. In this case, your pivot element will be the element 2. Since 1 > 2 is false, 1 is added to the list l. Since 2 > 2 is false, 2 is added to the list l. As a result, your recursive call on the list l will have exactly the same arguments as your original call, causing infinite recursion.

To fix this, try splitting the input into three lists - one of smaller values, one of equal values, and one of greater values. This code is shown here:

function sort(data){   if (data.length < 2){     return data;   } else {     var l = [];     var r = [];     var e = [];     var i = 0;     var pivot = (data.length / 2) | 0;      for(i = 0; i < data.length; i++) {       if (data[i] > data[pivot]) {         r.push(data[i]);       } else if (data[i] < data[pivot]) {         l.push(data[i]);       } else {         e.push(data[i]);       }     }       return sort(l).concat(e, sort(r));    } } 

This new version explicitly groups the equal elements into their own list, so they aren't recursively sorted by either of the recursive calls. It also gracefully handles duplicate elements.

Hope this helps!