Javascript quicksort algorithm implementation

Question

Javascript quicksort algorithm implementation

So I'm very new to javascript (came from c) and just started to learn the syntax, practicing with some exercises. I implemented a quicksort algorithm:

function sort(a)
{
    var _sort = function(l, r)
    {
        if (l >= r - 1)
            return;
        var p = r - 1;
        var y = l;
        var tmp;
        for (var i = l; i < r - 1; i++)
            if (a[i] < a[p])
            {
                tmp = a[i];
                a[i] = a[y];
                a[y] = tmp;
                y++;
            }
        tmp = a[y];
        a[y] = a[r - 1];
        a[r - 1] = tmp;
        _sort(l, y);
        _sort(y + 1, r);
    }

    _sort(0, a.length);
}

It works fine for small arrays, however for arrays beyond 5000 elements I get stack size limit exceeded. I tried to increase it, but that didn't work. I suspect there's something wrong with the way I implemented the algorithm, can it be?

My question is, how should I implement the algorithm, or bypass the stack size limitation (I think 5000 elements arrays are small), in order to make it work? I would be also glad with any style suggestions.

javascript
node.js
quicksort

Answer 1

You can simulate the stack with an array, which can be longer. I did very limited testing with this, but it seemed to work.

function sort(a) {
  var stack = [[0, a.length]];
  while (1) {
    var stackLength = stack.length;
    if (! stackLength) {
      break;
    }
    var l = stack[stackLength - 1][0], 
        r = stack[stackLength - 1][1];
    if (l >= r - 1) {
      stack.pop();
      continue;
    }
    var p = r - 1;
    var y = l;
    var tmp;
    for (var i = l; i < r - 1; i++)
      if (a[i] < a[p])
    {
      tmp = a[i];
      a[i] = a[y];
      a[y] = tmp;
      y++;
    }
    tmp = a[y];
    a[y] = a[r - 1];
    a[r - 1] = tmp;
    stack.pop();
    stack.push([y + 1, r]);
    stack.push([l, y]);
  }
  return a;
}

Answer 2

As you know, quicksort has pathologically bad performance for input that is already sorted or reverse sorted. In these cases you end up using O(n) stack space, which can lead to a stack overflow error.

To avoid these problem cases you could choose the pivot element "y" as the median of three (first, middle and last), though apparently there are sequences that trigger pathological performance even then. To completely rid yourself of this problem you could implement merge sort or heap sort instead. Or use an array as a stack instead of using recursion.