From 69156911be239c20899837603c9d2b54c37e9639 Mon Sep 17 00:00:00 2001
From: olehougaard <olehougaard@ce2b1a6d-e550-0410-aec6-3dcde31c8c00>
Date: Thu, 25 Sep 2008 11:28:02 +0000
Subject: [PATCH] Using quick sort for arrays.

Using quick sort in ArraySort instead of heap sort for better performance.
Review URL: http://codereview.chromium.org/4065

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@374 ce2b1a6d-e550-0410-aec6-3dcde31c8c00
---
 src/array.js               | 65 ++++++++++++++++------------------------------
 src/date-delay.js          |  2 --
 src/math.js                |  4 ++-
 test/mjsunit/array-sort.js | 13 ++++++++++
 4 files changed, 38 insertions(+), 46 deletions(-)

diff --git a/src/array.js b/src/array.js
index a62cf4d..953fe64 100644
--- a/src/array.js
+++ b/src/array.js
@@ -31,7 +31,6 @@
 
 // -------------------------------------------------------------------
 
-
 // Global list of arrays visited during toString, toLocaleString and
 // join invocations.
 var visited_arrays = new $Array();
@@ -669,53 +668,33 @@ function ArraySort(comparefn) {
     else return x < y ? -1 : 1;
   };
 
+  function QuickSort(a, from, to) {
+    if (from >= to - 1) return;
+    var pivot_index = $floor($random() * (to - from)) + from;
+    var pivot = a[pivot_index];
+    a[pivot_index] = a[to - 1];
+    a[to - 1] = pivot;
+    var partition = from;
+    for (var i = from; i < to - 1; i++) {
+      var element = a[i];
+      if (Compare(element, pivot) < 0) {
+        a[i] = a[partition];
+        a[partition] = element;
+        partition++;
+      }
+    }
+    a[to - 1] = a[partition];
+    a[partition] = pivot;
+    QuickSort(a, from, partition);
+    QuickSort(a, partition + 1, to);
+  }
+
   var old_length = ToUint32(this.length);
 
   %RemoveArrayHoles(this);
 
   var length = ToUint32(this.length);
-
-  // Bottom-up max-heap construction.
-  for (var i = 1; i < length; ++i) {
-    var child_index = i;
-    while (child_index > 0) {
-      var parent_index = ((child_index + 1) >> 1) - 1;
-      var parent_value = this[parent_index], child_value = this[child_index];
-      if (Compare(parent_value, child_value) < 0) {
-        this[parent_index] = child_value;
-        this[child_index] = parent_value;
-      } else {
-        break;
-      }
-      child_index = parent_index;
-    }
-  }
-
-  // Extract element and create sorted array.
-  for (var i = length - 1; i > 0; --i) {
-    // Put the max element at the back of the array.
-    var t0 = this[0]; this[0] = this[i]; this[i] = t0;
-    // Sift down the new top element.
-    var parent_index = 0;
-    while (true) {
-      var child_index = ((parent_index + 1) << 1) - 1;
-      if (child_index >= i) break;
-      var child1_value = this[child_index];
-      var child2_value = this[child_index + 1];
-      var parent_value = this[parent_index];
-      if (child_index + 1 >= i || Compare(child1_value, child2_value) > 0) {
-        if (Compare(parent_value, child1_value) > 0) break;
-        this[child_index] = parent_value;
-        this[parent_index] = child1_value;
-        parent_index = child_index;
-      } else {
-        if (Compare(parent_value, child2_value) > 0) break;
-        this[child_index + 1] = parent_value;
-        this[parent_index] = child2_value;
-        parent_index = child_index + 1;
-      }
-    }
-  }
+  QuickSort(this, 0, length);
 
   // We only changed the length of the this object (in
   // RemoveArrayHoles) if it was an array.  We are not allowed to set
diff --git a/src/date-delay.js b/src/date-delay.js
index d45883d..d9b8650 100644
--- a/src/date-delay.js
+++ b/src/date-delay.js
@@ -35,8 +35,6 @@
 // has the added benefit that the code in this file is isolated from
 // changes to these properties.
 const $Date = global.Date;
-const $floor = $Math_floor;
-const $abs = $Math_abs;
 
 
 // ECMA 262 - 15.9.1.2
diff --git a/src/math.js b/src/math.js
index cb5cfb9..6127d5f 100644
--- a/src/math.js
+++ b/src/math.js
@@ -30,7 +30,9 @@
 // has the added benefit that the code in this file is isolated from
 // changes to these properties.
 const $Infinity = global.Infinity;
-
+const $floor = $Math_floor;
+const $random = $Math_random;
+const $abs = $Math_abs;
 
 // Instance class name can only be set on functions. That is the only
 // purpose for MathConstructor.
diff --git a/test/mjsunit/array-sort.js b/test/mjsunit/array-sort.js
index 49d5b38..8afaea5 100644
--- a/test/mjsunit/array-sort.js
+++ b/test/mjsunit/array-sort.js
@@ -118,3 +118,16 @@ function TestObjectSort() {
 }
 
 TestObjectSort();
+
+// Test array sorting with holes in the array.
+function TestArraySortingWithHoles() {
+  var a = [];
+  a[4] = "18";
+  a[10] = "12";
+  a.sort();
+  assertEquals(11, a.length);
+  assertEquals("12", a[0]);
+  assertEquals("18", a[1]);
+}
+
+TestArraySortingWithHoles();
-- 
2.7.4