src/QuickSort.js

var quick_sort = function(unsorted) {
  if (unsorted.size <= 1)
    return unsorted;

  var pivot = unsorted.pop();
  var less = new Array();
  var greater = new Array();

  unsorted.forEach(function(element){
    if (element > pivot)
      less.push(element);
    else
      greater.push(element);
  });

  return quick_sort(less) + [pivot] + quick_sort(greater);
};

spec/QuickSort.js

describe("#quick_sort", function() {

  it("should sort the unsorted array", function() {
    var unsorted = [8, 2, 10, 5, 4, 9, 7, 1, 6, 3];
    var sorted = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    expect(quick_sort(unsorted)).toEqual(sorted);
  });

});

Error message

RangeError: Maximum call stack size exceeded
    at Array.forEach (native)
    at quick_sort (file://localhost/Users/jasonkim/projects/algorithm-everyday/quick_sort/javascript/src/QuickSort.js:9:12)
    at quick_sort (file://localhost/Users/jasonkim/projects/algorithm-everyday/quick_sort/javascript/src/QuickSort.js:16:10)

I am trying to test quick sort function using jasminejs. I am getting the error above. I have the terminating condition above if (unsorted.size <= 1) { return unsorted }. I am not sure why it's not terminating and goes into infinite loop.

src/QuickSort.js

var quick_sort = function(unsorted) {
  if (unsorted.size <= 1)
    return unsorted;

  var pivot = unsorted.pop();
  var less = new Array();
  var greater = new Array();

  unsorted.forEach(function(element){
    if (element > pivot)
      less.push(element);
    else
      greater.push(element);
  });

  return quick_sort(less) + [pivot] + quick_sort(greater);
};

spec/QuickSort.js

describe("#quick_sort", function() {

  it("should sort the unsorted array", function() {
    var unsorted = [8, 2, 10, 5, 4, 9, 7, 1, 6, 3];
    var sorted = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    expect(quick_sort(unsorted)).toEqual(sorted);
  });

});

Error message

RangeError: Maximum call stack size exceeded
    at Array.forEach (native)
    at quick_sort (file://localhost/Users/jasonkim/projects/algorithm-everyday/quick_sort/javascript/src/QuickSort.js:9:12)
    at quick_sort (file://localhost/Users/jasonkim/projects/algorithm-everyday/quick_sort/javascript/src/QuickSort.js:16:10)

I am trying to test quick sort function using jasminejs. I am getting the error above. I have the terminating condition above if (unsorted.size <= 1) { return unsorted }. I am not sure why it's not terminating and goes into infinite loop.

• javascript
• sorting
• jasmine

• 1 Don't know about jasmine.js, does unsorted.size actually mean unsorted.length? Also, + operator on arrays doesn't seem to work that way in pure JS. – Passerby Commented Aug 12, 2013 at 7:28
• @Passerby, thanks! Make that as an answer, and I'll accept it. Ruby syntax was getting to me. – Jason Kim Commented Aug 12, 2013 at 7:41

1 Answer 1

Your problem is the line

if (unsorted.size <= 1) return unsorted;

Which will never be reached as Arrays don't have a prototype property named size, hence you don't return the Array when unsorted is empty and therefore going into an infinite loop, calling quick_sort with an empty unsorted until the call stack is exhausted.

The property you are looking for is Array.prototype.length, if you would change the line to

if (unsorted.length <= 1) return unsorted;

You function would properly return if it gets an empty array passed.

However theres a little thing, which can be noticed too,

return quick_sort(less) + [pivot] + quick_sort(greater);

If you are expecting to return a concatenated sorted array, you would have to change this line too.

You cannot simply concatenate Array by using an + operator, which calls,

[[toPrimitive]] and [[toString]] on lRef and rRef resulting in an concatenated String representation of your array.

Which would (as you are effectivley +'ing all the pivot arrays, containing a single element) in something like 10987654321, instead of [10,9,8,7,6,5,4,3,2,1] what you may achieve.

Instead use Array.prototype.concat which concatenates arrays.

return quick_sort(less).concat([pivot]).concat(quick_sort(greater));

Here is a Fiddle