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.

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

• Could you please provide an example by using jsfiddle ? – Vadim Ivanov Commented Jul 21, 2013 at 0:33
• 1 You do know that javascript alread has an Array.sort method, and in at least some browsers that will use the quicksort algorithm for certain arrays, so you're really reinventing the wheel here ? – adeneo Commented Jul 21, 2013 at 0:33
• 1 @adeneo, I am aware of that. Whenever I learn some new language syntax, I do exercises like this. – kaspersky Commented Jul 21, 2013 at 0:37
• It looks like there's nothing wrong with your function, you could use a stack data structure to avoid the stackoverflow which as you know can happen with deep recursion – aaronman Commented Jul 21, 2013 at 0:37
• 1 @adeneo I've considered this question as matter of curiosity. The same you can say about most of the language, that they have implementation of Array.sort method. Just for curiosity why not to implement it during the study language =) – Vadim Ivanov Commented Jul 21, 2013 at 0:38

2 Answers 2

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

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 pletely 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.