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));
    }
}

Solution 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!

Solution 2

If you pick the largest value of the array as the pivot element, then all values of data will end up in the array l and none in r. Thus will make the recursion never stop (and keep l, r and pivot at the same values). Unless this is a brain excercise, using data.sort() should do a better job. ;)

Comments

[templatetypedef]

@Bergi- Thanks! I'm by no means a JS programmer, and I didn't know that you could do that.

[Lester Peabody]

gg Randall. Let's get some stats on API access calls against the sort tag? :)

[Vicky Chijwani]

I bet @templatetypedef gained a lot of reputation today because of that stacksort implementation :)

[vlasits]

Up voted solely because this worked in the hilarious stacksort project (gkoberger.github.com/stacksort)

[Cyril N.]

And @templatetypedef is wondering why is answer is having so much popularity now ... thanks to stacksort ;)

[templatetypedef]

@glebm If I'm not mistaken, the memory usage here is proportional to the runtime, so this only uses O(n^2) memory in degenerate cases.

[glebm]

@templatetypedef Yes, O(n log n) on average, O(n^2) when every pivot ends up to the left every time

[Gorm Casper]

First stacksort result that doesn't use Array.prototype.sort()