js/src/builtin/Sorting.js

   1 /* This Source Code Form is subject to the terms of the Mozilla Public
   2  * License, v. 2.0. If a copy of the MPL was not distributed with this
   3  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   4
   5 // We use varying sorts across the self-hosted codebase. All sorts are
   6 // consolidated here to avoid confusion and re-implementation of existing
   7 // algorithms.
   8
   9 // For sorting small typed arrays.
  10 function InsertionSort(array, from, to, comparefn) {
  11   var item, swap, i, j;
  12   for (i = from + 1; i <= to; i++) {
  13     item = array[i];
  14     for (j = i - 1; j >= from; j--) {
  15       swap = array[j];
  16       if (callContentFunction(comparefn, undefined, swap, item) <= 0) {
  17         break;
  18       }
  19       array[j + 1] = swap;
  20     }
  21     array[j + 1] = item;
  22   }
  23 }
  24
  25 // A helper function for MergeSortTypedArray.
  26 //
  27 // Merge comparefn-sorted slices list[start..<=mid] and list[mid+1..<=end],
  28 // storing the merged sequence in out[start..<=end].
  29 function MergeTypedArray(list, out, start, mid, end, comparefn) {
  30   // Skip lopsided runs to avoid doing useless work.
  31   // Skip calling the comparator if the sub-list is already sorted.
  32   if (
  33     mid >= end ||
  34     callContentFunction(comparefn, undefined, list[mid], list[mid + 1]) <= 0
  35   ) {
  36     for (var i = start; i <= end; i++) {
  37       out[i] = list[i];
  38     }
  39     return;
  40   }
  41
  42   var i = start;
  43   var j = mid + 1;
  44   var k = start;
  45   while (i <= mid && j <= end) {
  46     var lvalue = list[i];
  47     var rvalue = list[j];
  48     if (callContentFunction(comparefn, undefined, lvalue, rvalue) <= 0) {
  49       out[k++] = lvalue;
  50       i++;
  51     } else {
  52       out[k++] = rvalue;
  53       j++;
  54     }
  55   }
  56
  57   // Empty out any remaining elements.
  58   while (i <= mid) {
  59     out[k++] = list[i++];
  60   }
  61   while (j <= end) {
  62     out[k++] = list[j++];
  63   }
  64 }
  65
  66 // Iterative, bottom up, mergesort. Optimized version for TypedArrays.
  67 function MergeSortTypedArray(array, len, comparefn) {
  68   assert(
  69     IsPossiblyWrappedTypedArray(array),
  70     "MergeSortTypedArray works only with typed arrays."
  71   );
  72
  73   // Use the same TypedArray kind for the buffer.
  74   var C = ConstructorForTypedArray(array);
  75
  76   var lBuffer = new C(len);
  77
  78   // Copy all elements into a temporary buffer, so that any modifications
  79   // when calling |comparefn| are ignored.
  80   for (var i = 0; i < len; i++) {
  81     lBuffer[i] = array[i];
  82   }
  83
  84   // Insertion sort for small arrays, where "small" is defined by performance
  85   // testing.
  86   if (len < 8) {
  87     InsertionSort(lBuffer, 0, len - 1, comparefn);
  88
  89     return lBuffer;
  90   }
  91
  92   // We do all of our allocating up front.
  93   var rBuffer = new C(len);
  94
  95   // Use insertion sort for the initial ranges.
  96   var windowSize = 4;
  97   for (var start = 0; start < len - 1; start += windowSize) {
  98     var end = std_Math_min(start + windowSize - 1, len - 1);
  99     InsertionSort(lBuffer, start, end, comparefn);
 100   }
 101
 102   for (; windowSize < len; windowSize = 2 * windowSize) {
 103     for (var start = 0; start < len; start += 2 * windowSize) {
 104       // The midpoint between the two subarrays.
 105       var mid = start + windowSize - 1;
 106
 107       // To keep from going over the edge.
 108       var end = std_Math_min(start + 2 * windowSize - 1, len - 1);
 109
 110       MergeTypedArray(lBuffer, rBuffer, start, mid, end, comparefn);
 111     }
 112
 113     // Swap both lists.
 114     var swap = lBuffer;
 115     lBuffer = rBuffer;
 116     rBuffer = swap;
 117   }
 118
 119   return lBuffer;
 120 }