Faster 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 630 matching lines @@
   }
   this.length = len - del_count + num_additional_args;
   
   // Return the deleted elements.
   return deleted_elements;
 };
 
 
 function ArraySort(comparefn) {
   // In-place QuickSort algorithm.
+  // For short (length <= 22) arrays, insertion sort is used for efficiency.
 
   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 InsertionSort(a, from, to) {
+    for(var i = from + 1; i < to; i++) {

[Christian Plesner Hansen, 2008/09/30 09:50:56]

There should be a space between 'for' and '('.

+      var element = a[i];
+      // place element in a[from..i[
+      // binary search
+      var min = from;
+      var max = i;
+      while(min < max) {
+        var mid = min + ((max - min) >> 1);
+        var order = Compare(a[mid], element);
+        if (order == 0) {
+          min = max = mid;
+          break;
+        }
+        if (order < 0) {
+          min = mid + 1;
+        } else {
+          max = mid;

[Christian Plesner Hansen, 2008/09/30 09:50:56]

I'm not 100% sure but I think this should be max = mid - 1.

+        }
+      }
+      // place element at position min==max.
+      for(var j = min; j < i; j++) {
+        var tmp = a[j];
+        a[j] = element;
+        element = tmp;
+      }
+      a[i] = element;
+    }
+  }
+  
   function QuickSort(a, from, to) {
-    if (from >= to - 1) return;
+    // Insertion sort is faster for short arrays.
+    if (to - from <= 22) { 
+      InsertionSort(a, from, to);
+      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.
     a[pivot_index] = a[to - 1];
     a[to - 1] = pivot;
     var low_end = from;   // Upper bound of the elements lower than pivot.
     var high_start = to - 1; // Lower bound of the elements greater than pivot.
     for (var i = from; i < high_start; ) {
       var element = a[i];
@@ skipping 228 matching lines @@
     ArrayEvery: 1,
     ArrayMap: 1,
     ArrayIndexOf: 1,
     ArrayLastIndexOf: 1,
     ArrayPush: 1
   });
 };
 
 
 SetupArray();