Using quick sort for arrays....

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 630 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.

[mdakin, 2008/09/25 14:25:28]

I think it is Quicksort now.

 
   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 = global.Math.floor(global.Math.random() * (to - from)) + from;

[Mads Ager (chromium), 2008/09/24 12:34:43]

We need to make sure that we use the original Math.floor and Math.random so that
user-defined versions of Math.random do not interfere with this code.  See for
instance date-delay.js that introduces and uses $floor and $abs for the original
versions of Math.floor and Math.abs.

+    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);

[mdakin, 2008/09/25 14:25:28]

Maybe using insertion sort for small arrays (<10 elements ) would be good. It is
faster than Quicksort for small arrays.

-
-  // 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;
-      }
-    }
-  }
-
-  // We only changed the length of the this object (in
-  // RemoveArrayHoles) if it was an array.  We are not allowed to set
-  // the length of the this object if it is not an array because this
-  // might introduce a new length property.
-  if (IS_ARRAY(this)) {

[Mads Ager (chromium), 2008/09/24 12:34:43]

This piece of code should still be needed.  If we remove array holes, we have to
restore the length afterwards.

-    this.length = old_length;
-  }
-
+  QuickSort(this, 0, length);
   return this;
 };
 
 
 // The following functions cannot be made efficient on sparse arrays while
 // preserving the semantics, since the calls to the receiver function can add
 // or delete elements from the array.
 
 function ArrayFilter(f, receiver) {
   if (!IS_FUNCTION(f)) {
@@ skipping 181 matching lines @@
     ArrayEvery: 1,
     ArrayMap: 1,
     ArrayIndexOf: 1,
     ArrayLastIndexOf: 1,
     ArrayPush: 1
   });
 };
 
 
 SetupArray();