From 8cd31d295bb7a1c3ae457f1c2ebdfac26a4b35ac Mon Sep 17 00:00:00 2001
From: "lrn@chromium.org"
 <lrn@chromium.org@ce2b1a6d-e550-0410-aec6-3dcde31c8c00>
Date: Tue, 17 Feb 2009 08:56:36 +0000
Subject: [PATCH] Array sort was changed in a way that completely undid another
 optimization.

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@1288 ce2b1a6d-e550-0410-aec6-3dcde31c8c00
---
 src/array.js | 29 +++++++++++++----------------
 1 file changed, 13 insertions(+), 16 deletions(-)

diff --git a/src/array.js b/src/array.js
index 82192b0..d30a989 100644
--- a/src/array.js
+++ b/src/array.js
@@ -683,29 +683,26 @@ function ArraySort(comparefn) {
       (custom_compare || %_IsSmi(pivot)) ? pivot : ToString(pivot);
     // Issue 95: Keep the pivot element out of the comparisons to avoid
     // infinite recursion if comparefn(pivot, pivot) != 0.
-    var low_end = from; // Upper bound of the elements lower than pivot.
-    var high_start = to; // Lower bound of the elements greater than pivot.
-    var eq_start = to - 1; // Lower bound of elements equal to pivot.
-    a[pivot_index] = a[eq_start];
-    a[eq_start] = pivot;
-    // From eq_start to high_start are elements equal to the pivot
-    // (including the pivot).
-    // From low_end to eq_start are elements that have not been compared yet.
-    while (low_end < eq_start) {
-      var element = a[low_end];
+    a[pivot_index] = a[from];
+    a[from] = pivot;
+    var low_end = from;   // Upper bound of the elements lower than pivot.
+    var high_start = to;  // Lower bound of the elements greater than pivot.
+    // From low_end to i are elements equal to pivot.
+    // From i to high_start are elements that haven't been compared yet.
+    for (var i = from + 1; i < high_start; ) {
+      var element = a[i];
       var order = Compare(element, pivot_key);
       if (order < 0) {
+        a[i] = a[low_end];
+        a[low_end] = element;
+        i++;
         low_end++;
       } else if (order > 0) {
-        eq_start--;
         high_start--;
-        a[low_end] = a[eq_start];
-        a[eq_start] = a[high_start];
+        a[i] = a[high_start];
         a[high_start] = element;
       } else {  // order == 0
-        eq_start--;
-        a[low_end] = a[eq_start];
-        a[eq_start] = element;
+        i++;
       }
     }
     QuickSort(a, from, low_end);
-- 
2.7.4