Unify treatment of sorting with and without custom comparator.

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 626 matching lines @@
 
   // 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.
 
-  var global_receiver;
+  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 InsertionSortWithFunc(a, from, to) {
+  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 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;
-    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[from];
-    a[from] = pivot;
-    var low_end = from;   // Upper bound of the elements lower than pivot.
-    var high_start = to;  // Lower bound of the elements greater than 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; ) {
-      var element = a[i];
-      var order = %_CallFunction(global_receiver, element, pivot, comparefn);
-      if (order < 0) {
-        a[i] = a[low_end];
-        a[low_end] = element;
-        i++;
-        low_end++;
-      } else if (order > 0) {
-        high_start--;
-        a[i] = a[high_start];
-        a[high_start] = element;
-      } else {  // order == 0
-        i++;
-      }
-    }
-    QuickSortWithFunc(a, from, low_end);
-    QuickSortWithFunc(a, high_start, to);
-  }
-
-  function Compare(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;
-  };
-
-  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 = Compare(tmp, element);
-        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);
       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[from];
     a[from] = pivot;
     var low_end = from;   // Upper bound of the elements lower than pivot.
     var high_start = to;  // Lower bound of the elements greater than 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; ) {
       var element = a[i];
-      var order = Compare(element, pivot);
+      var order = %_CallFunction(global_receiver, element, pivot, comparefn);
       if (order < 0) {
         a[i] = a[low_end];
         a[low_end] = element;
         i++;
         low_end++;
       } else if (order > 0) {
         high_start--;
         a[i] = a[high_start];
         a[high_start] = element;
       } else {  // order == 0
@@ skipping 139 matching lines @@
   }
 
   var num_non_undefined = %RemoveArrayHoles(this, length);
   if (num_non_undefined == -1) {
     // There were indexed accessors in the array.  Move array holes and
     // undefineds to the end using a Javascript function that is safe
     // in the presence of accessors.
     num_non_undefined = SafeRemoveArrayHoles(this);
   }
 
-  if(IS_FUNCTION(comparefn)) {
-    global_receiver = %GetGlobalReceiver();
-    QuickSortWithFunc(this, 0, num_non_undefined);
-  } else {
-    QuickSort(this, 0, num_non_undefined);
-  }
+  QuickSort(this, 0, num_non_undefined);
 
   if (!is_array && (num_non_undefined + 1 < max_prototype_element)) {
     // For compatibility with JSC, we shadow any elements in the prototype
     // chain that has become exposed by sort moving a hole to its position.
     ShadowPrototypeElements(this, num_non_undefined, max_prototype_element);
   }
 
   return this;
 }
 
@@ skipping 255 matching lines @@
     "lastIndexOf", getFunction("lastIndexOf", ArrayLastIndexOf, 1),
     "reduce", getFunction("reduce", ArrayReduce, 1),
     "reduceRight", getFunction("reduceRight", ArrayReduceRight, 1)
   ));
 
   %FinishArrayPrototypeSetup($Array.prototype);
 }
 
 
 SetupArray();