Tuning quick sort....

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 629 matching lines @@
     this[i++] = %_Arguments(arguments_index++);
   }
   this.length = len - del_count + num_additional_args;
   
   // Return the deleted elements.
   return deleted_elements;
 };
 
 
 function ArraySort(comparefn) {
-  // Standard in-place HeapSort algorithm.
+  // In-place QuickSort algorithm.
 
   function Compare(x,y) {
     if (IS_UNDEFINED(x)) {
       if (IS_UNDEFINED(y)) return 0;
       return 1;
     }
     if (IS_UNDEFINED(y)) return -1;
 
     if (IS_FUNCTION(comparefn)) {
       return comparefn.call(null, x, y);
     }
     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;
   };
 
   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 low_end = from;   // Upper bound of the elements lower than pivot.
+    var high_start = to; // Lower bound of the elements greater than pivot.
+    for (var i = from; i < high_start; ) {
       var element = a[i];
-      if (Compare(element, pivot) < 0) {
-        a[i] = a[partition];
-        a[partition] = element;
-        partition++;
+      var order = Compare(element, pivot);
+      if (order < 0) {
+        a[i] = a[low_end];
+        a[low_end] = element;
+        low_end++;
+        i++;
+      } else if (order > 0) {
+        high_start--;
+        a[i] = a[high_start];
+        a[high_start] = element;
+      } else { // order == 0
+        i++;
       }
     }
-    a[to - 1] = a[partition];
-    a[partition] = pivot;
-    QuickSort(a, from, partition);
-    QuickSort(a, partition + 1, to);
+    QuickSort(a, from, low_end);
+    QuickSort(a, high_start, to);
   }
 
   var old_length = ToUint32(this.length);
 
   %RemoveArrayHoles(this);
 
   var length = ToUint32(this.length);
   QuickSort(this, 0, length);
 
   // We only changed the length of the this object (in
@@ skipping 198 matching lines @@
     ArrayEvery: 1,
     ArrayMap: 1,
     ArrayIndexOf: 1,
     ArrayLastIndexOf: 1,
     ArrayPush: 1
   });
 };
 
 
 SetupArray();