Avoid arbitrarily deep recursion in Array.sort.

src/array.js

Index: src/array.js
===================================================================
--- src/array.js	(revision 11836)
+++ src/array.js	(working copy)
@@ -778,77 +778,84 @@
   };
 
   var QuickSort = function QuickSort(a, from, to) {
-    // Insertion sort is faster for short arrays.
-    if (to - from <= 10) {
-      InsertionSort(a, from, to);
-      return;
-    }
-    // Find a pivot as the median of first, last and middle element.
-    var v0 = a[from];
-    var v1 = a[to - 1];
-    var middle_index = from + ((to - from) >> 1);
-    var v2 = a[middle_index];
-    var c01 = %_CallFunction(receiver, v0, v1, comparefn);
-    if (c01 > 0) {
-      // v1 < v0, so swap them.
-      var tmp = v0;
-      v0 = v1;
-      v1 = tmp;
-    } // v0 <= v1.
-    var c02 = %_CallFunction(receiver, v0, v2, comparefn);
-    if (c02 >= 0) {
-      // v2 <= v0 <= v1.
-      var tmp = v0;
-      v0 = v2;
-      v2 = v1;
-      v1 = tmp;
-    } else {
-      // v0 <= v1 && v0 < v2
-      var c12 = %_CallFunction(receiver, v1, v2, comparefn);
-      if (c12 > 0) {
-        // v0 <= v2 < v1
-        var tmp = v1;
-        v1 = v2;
-        v2 = tmp;
+    while (true) {
+      // Insertion sort is faster for short arrays.
+      if (to - from <= 10) {
+        InsertionSort(a, from, to);
+        return;
       }
-    }
-    // v0 <= v1 <= v2
-    a[from] = v0;
-    a[to - 1] = v2;
-    var pivot = v1;
-    var low_end = from + 1;   // Upper bound of elements lower than pivot.
-    var high_start = to - 1;  // Lower bound of elements greater than pivot.
-    a[middle_index] = a[low_end];
-    a[low_end] = pivot;
+      // Find a pivot as the median of first, last and middle element.
+      var v0 = a[from];
+      var v1 = a[to - 1];
+      var middle_index = from + ((to - from) >> 1);
+      var v2 = a[middle_index];
+      var c01 = %_CallFunction(receiver, v0, v1, comparefn);
+      if (c01 > 0) {
+        // v1 < v0, so swap them.
+        var tmp = v0;
+        v0 = v1;
+        v1 = tmp;
+      } // v0 <= v1.
+      var c02 = %_CallFunction(receiver, v0, v2, comparefn);
+      if (c02 >= 0) {
+        // v2 <= v0 <= v1.
+        var tmp = v0;
+        v0 = v2;
+        v2 = v1;
+        v1 = tmp;
+      } else {
+        // v0 <= v1 && v0 < v2
+        var c12 = %_CallFunction(receiver, v1, v2, comparefn);
+        if (c12 > 0) {
+          // v0 <= v2 < v1
+          var tmp = v1;
+          v1 = v2;
+          v2 = tmp;
+        }
+      }
+      // v0 <= v1 <= v2
+      a[from] = v0;
+      a[to - 1] = v2;
+      var pivot = v1;
+      var low_end = from + 1;   // Upper bound of elements lower than pivot.
+      var high_start = to - 1;  // Lower bound of elements greater than pivot.
+      a[middle_index] = a[low_end];
+      a[low_end] = pivot;
 
-    // From low_end to i are elements equal to pivot.
-    // From i to high_start are elements that haven't been compared yet.
-    partition: for (var i = low_end + 1; i < high_start; i++) {
-      var element = a[i];
-      var order = %_CallFunction(receiver, element, pivot, comparefn);
-      if (order < 0) {
-        a[i] = a[low_end];
-        a[low_end] = element;
-        low_end++;
-      } else if (order > 0) {
-        do {
-          high_start--;
-          if (high_start == i) break partition;
-          var top_elem = a[high_start];
-          order = %_CallFunction(receiver, top_elem, pivot, comparefn);
-        } while (order > 0);
-        a[i] = a[high_start];
-        a[high_start] = element;
+      // From low_end to i are elements equal to pivot.
+      // From i to high_start are elements that haven't been compared yet.
+      partition: for (var i = low_end + 1; i < high_start; i++) {
+        var element = a[i];
+        var order = %_CallFunction(receiver, element, pivot, comparefn);
         if (order < 0) {
-          element = a[i];
           a[i] = a[low_end];
           a[low_end] = element;
           low_end++;
+        } else if (order > 0) {
+          do {
+            high_start--;
+            if (high_start == i) break partition;
+            var top_elem = a[high_start];
+            order = %_CallFunction(receiver, top_elem, pivot, comparefn);
+          } while (order > 0);
+          a[i] = a[high_start];
+          a[high_start] = element;
+          if (order < 0) {
+            element = a[i];
+            a[i] = a[low_end];
+            a[low_end] = element;
+            low_end++;
+          }
         }
       }
+      if (to - high_start < low_end - from) {
+        QuickSort(a, high_start, to);
+        to = low_end;
+      } else {
+        QuickSort(a, from, low_end);
+        from = high_start;
+      }
     }
-    QuickSort(a, from, low_end);
-    QuickSort(a, high_start, to);
   };
 
   // Copy elements in the range 0..length from obj's prototype chain