1 files changed, 88 insertions, 63 deletions

diff --git a/deps/v8/src/array.js b/deps/v8/src/array.js
index a1cc5b6a7d..1cedd8d476 100644
--- a/deps/v8/src/array.js
+++ b/deps/v8/src/array.js
@@ -777,78 +777,103 @@ function ArraySort(comparefn) {
     }
   };
 
-  var QuickSort = function QuickSort(a, from, to) {
-    // Insertion sort is faster for short arrays.
-    if (to - from <= 10) {
-      InsertionSort(a, from, to);
-      return;
+  var GetThirdIndex = function(a, from, to) {
+    var t_array = [];
+    // Use both 'from' and 'to' to determine the pivot candidates.
+    var increment = 200 + ((to - from) & 15);
+    for (var i = from + 1; i < to - 1; i += increment) {
+      t_array.push([i, a[i]]);
     }
-    // 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;
+    t_array.sort(function(a, b) {
+        return %_CallFunction(receiver, a[1], b[1], comparefn) } );
+    var third_index = t_array[t_array.length >> 1][0];
+    return third_index;
+  }
+
+  var QuickSort = function QuickSort(a, from, to) {
+    var third_index = 0;
+    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;
-
-    // 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;
+      if (to - from > 1000) {
+        third_index = GetThirdIndex(a, from, to);
+      } else {
+        third_index = from + ((to - from) >> 1);
+      }
+      // Find a pivot as the median of first, last and middle element.
+      var v0 = a[from];
+      var v1 = a[to - 1];
+      var v2 = a[third_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[third_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) {
-          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