Reimplement InsertSort to use simple linear search.

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 631 matching lines @@
 
 function ArraySort(comparefn) {
   // In-place QuickSort algorithm.
   // For short (length <= 22) arrays, insertion sort is used for efficiency.
 
   var global_receiver;
 
   function InsertionSortWithFunc(a, from, to) {
     for (var i = from + 1; i < to; i++) {
       var element = a[i];
-      // place element in a[from..i[
-      // binary search
-      var min = from;
-      var max = i;
-      // The search interval is a[min..max[
-      while (min < max) {
-        var mid = min + ((max - min) >> 1);
-        var order = %_CallFunction(global_receiver, a[mid], element, comparefn);
-        if (order == 0) {
-          min = max = mid;
+      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;
         }
-        if (order < 0) {
-          min = mid + 1;
-        } else {
-          max = mid;
-        }
       }
-      // place element at position min==max.
-      for (var j = i; j > min; j--) {
-        a[j] = a[j - 1];
-      }
-      a[min] = element;
+      a[j + 1] = element;
     }
   }
 
   function QuickSortWithFunc(a, from, to) {
     // Insertion sort is faster for short arrays.
     if (to - from <= 22) {
       InsertionSortWithFunc(a, from, to);
       return;
     }
     var pivot_index = $floor($random() * (to - from)) + from;
@@ skipping 20 matching lines @@
         a[high_start] = element;
       } else {  // order == 0
         i++;
       }
     }
     QuickSortWithFunc(a, from, low_end);
     QuickSortWithFunc(a, high_start, to);
   }
 
   function Compare(x,y) {
-    // Assume the comparefn, if any, is a consistent comparison function.
-    // If it isn't, we are allowed arbitrary behavior by ECMA 15.4.4.11.
     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;
   };
 
   function InsertionSort(a, from, to) {
     for (var i = from + 1; i < to; i++) {
       var element = a[i];
-      // Pre-convert the element to a string for comparison if we know
-      // it will happen on each compare anyway.
       var key = %_IsSmi(element) ? element : ToString(element);

[Lasse Reichstein, 2010/04/12 07:35:42]

I'm very much attached to this line, but on the other hand, the most common uses
of sort-with-default-comparison is on numbers and strings, so it might just be
overhead.

Keep it, but maybe try a test run later without this line and see if it makes a
difference in any direction.

[antonm, 2010/04/12 15:24:25]

Sure.  Sending to golem in no time.

-      // place element in a[from..i[
-      // binary search
-      var min = from;
-      var max = i;
-      // The search interval is a[min..max[
-      while (min < max) {
-        var mid = min + ((max - min) >> 1);
-        var order = Compare(a[mid], key);
-        if (order == 0) {
-          min = max = mid;
+      for (var j = i - 1; j >= from; j--) {
+        var tmp = a[j];
+        var order = Compare(tmp, key);
+        if (order > 0) {
+          a[j + 1] = tmp;
+        } else {
           break;
         }
-        if (order < 0) {
-          min = mid + 1;
-        } else {
-          max = mid;
-        }
       }
-      // place element at position min==max.
-      for (var j = i; j > min; j--) {
-        a[j] = a[j - 1];
-      }
-      a[min] = element;
+      a[j + 1] = element;
     }
   }
 
   function QuickSort(a, from, to) {
     // Insertion sort is faster for short arrays.
     if (to - from <= 22) {
       InsertionSort(a, from, to);
       return;
     }
     var pivot_index = $floor($random() * (to - from)) + from;
@@ skipping 445 matching lines @@
     "lastIndexOf", getFunction("lastIndexOf", ArrayLastIndexOf, 1),
     "reduce", getFunction("reduce", ArrayReduce, 1),
     "reduceRight", getFunction("reduceRight", ArrayReduceRight, 1)
   ));
 
   %FinishArrayPrototypeSetup($Array.prototype);
 }
 
 
 SetupArray();