Change quicksort pivot from random to median-of-three.

src/array.js

 // Copyright 2006-2008 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 623 matching lines @@
   while (arguments_index < arguments_length) {
     this[i++] = %_Arguments(arguments_index++);
   }
   this.length = len - del_count + num_additional_args;
 
   // Return the deleted elements.
   return deleted_elements;
 }
 
 
+function InsertionSort(a, from, to, comparefn, global_receiver) {
+  for (var i = from + 1; i < to; i++) {
+    var element = a[i];
+    for (var j = i - 1; j >= from; j--) {
+      var tmp = a[j];
+      var order = %_CallFunction(global_receiver, tmp, element, comparefn);
+      if (order > 0) {
+        a[j + 1] = tmp;
+      } else {
+        break;
+      }
+    }
+    a[j + 1] = element;
+  }

[Karl Klose, 2010/12/17 09:55:37]

Consider putting InsertionSort back into ArraySort, so that it is on the same
level as QuickSort

[Lasse Reichstein, 2010/12/17 10:04:22]

Done.
It was an attempt at a micro-optimization, but its impact, if there is one, is
below the level of measurability.

+}
+
+
 function ArraySort(comparefn) {
   // In-place QuickSort algorithm.
   // For short (length <= 22) arrays, insertion sort is used for efficiency.
 
   if (!IS_FUNCTION(comparefn)) {
     comparefn = function (x, y) {
       if (x === y) return 0;
       if (%_IsSmi(x) && %_IsSmi(y)) {
         return %SmiLexicographicCompare(x, y);
       }
       x = ToString(x);
       y = ToString(y);
       if (x == y) return 0;
       else return x < y ? -1 : 1;
     };
   }
   var global_receiver = %GetGlobalReceiver();
 
-  function InsertionSort(a, from, to) {
-    for (var i = from + 1; i < to; i++) {
-      var element = a[i];
-      for (var j = i - 1; j >= from; j--) {
-        var tmp = a[j];
-        var order = %_CallFunction(global_receiver, tmp, element, comparefn);
-        if (order > 0) {
-          a[j + 1] = tmp;
-        } else {
-          break;
-        }
-      }
-      a[j + 1] = element;
-    }
-  }
-
   function QuickSort(a, from, to) {
     // Insertion sort is faster for short arrays.
-    if (to - from <= 22) {
-      InsertionSort(a, from, to);
+    if (to - from <= 13) {
+      InsertionSort(a, from, to, comparefn, global_receiver);
       return;
     }
-    var pivot_index = $floor($random() * (to - from)) + from;
-    var pivot = a[pivot_index];
-    // Issue 95: Keep the pivot element out of the comparisons to avoid
-    // infinite recursion if comparefn(pivot, pivot) != 0.
-    %_SwapElements(a, from, pivot_index);
-    var low_end = from;   // Upper bound of the elements lower than pivot.
-    var high_start = to;  // Lower bound of the elements greater than 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 = comparefn(v0, v1);
+    if (c01 > 0) {
+      // v1 < v0, so swap them.
+      var tmp = v0;
+      v0 = v1;
+      v1 = tmp;
+    } // v0 <= v1.
+    var c02 = comparefn(v0, v2);
+    if (c02 >= 0) {
+      // v2 <= v0 <= v1.
+      var tmp = v0;
+      v0 = v2;
+      v2 = v1;
+      v1 = tmp;
+    } else {
+      // v0 <= v1 && v0 < v2
+      var c12 = comparefn(v1, v2);
+      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 the elements lower than pivot.
+    var high_start = to - 1;  // Lower bound of the 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.
-    for (var i = from + 1; i < high_start; ) {
+    for (var i = low_end + 1; i < high_start; ) {
       var element = a[i];
       var order = %_CallFunction(global_receiver, element, pivot, comparefn);
       if (order < 0) {
         %_SwapElements(a, i, low_end);
         i++;
         low_end++;
       } else if (order > 0) {
         high_start--;
         %_SwapElements(a, i, high_start);
       } else {  // order == 0
         i++;
       }
     }
     QuickSort(a, from, low_end);
     QuickSort(a, high_start, to);
   }
 
   // Copies elements in the range 0..length from obj's prototype chain
   // to obj itself, if obj has holes. Returns one more than the maximal index
   // of a prototype property.

[Karl Klose, 2010/12/17 09:55:37]

Not in that change, but we should have consistent style in the comments. Copies
-> Copy, Returns -> Return.

[Lasse Reichstein, 2010/12/17 10:04:22]

Done.

   function CopyFromPrototype(obj, length) {
     var max = 0;
     for (var proto = obj.__proto__; proto; proto = proto.__proto__) {
       var indices = %GetArrayKeys(proto, length);
       if (indices.length > 0) {
         if (indices[0] == -1) {
           // It's an interval.
           var proto_length = indices[1];
           for (var i = 0; i < proto_length; i++) {
             if (!obj.hasOwnProperty(i) && proto.hasOwnProperty(i)) {
@@ skipping 448 matching lines @@
     "lastIndexOf", getFunction("lastIndexOf", ArrayLastIndexOf, 1),
     "reduce", getFunction("reduce", ArrayReduce, 1),
     "reduceRight", getFunction("reduceRight", ArrayReduceRight, 1)
   ));
 
   %FinishArrayPrototypeSetup($Array.prototype);
 }
 
 
 SetupArray();