Javascript的细节（四）：array#sort

function (array, length, compareFn) {
    const buffer = []
    buffer.__proto__ = null

let bucketSize = 2,
  lastSize = 1,
  position = 0
const doubleLength = length + length

    while (bucketSize < doubleLength) {
        while (position < length) {
            const left = position
            const mid = left + lastSize

            // perform a merge but only if it's necessary
            if (mid < length && compareFn(array[mid], array[mid - 1]) < 0) {

let right = position + bucketSize
right = right < length ? right : length
let i = mid - 1,
  j = 0,
  k = mid

while (k < right) {
  buffer[j++] = array[k++]
}

                let rightElement = buffer[--j]
                let leftElement = array[i]

                for (;;) {
                    if (compareFn(rightElement, leftElement) < 0) {
                        array[--k] = leftElement
                        if (i > left) {
                            leftElement = array[--i]
                        } else {
                            array[--k] = rightElement
                            break
                        }
                    } else {
                        array[--k] = rightElement
                        if (j > 0) {
                            rightElement = buffer[--j]
                        } else {
                            break
                        }
                    }
                }

                while (j > 0) {
                    array[--k] = buffer[--j]
                }
            }

            position += bucketSize
        }
        position = 0
        lastSize = bucketSize
        bucketSize *= 2
    }

    var sortFunction;
    if (typeof comparator == "function")
        sortFunction = comparatorSort;
    else if (comparator === @undefined)
        sortFunction = stringSort;
    else
        @throwTypeError("Array.prototype.sort requires the comparsion function be a function or undefined");

    function bucketSort(array, dst, bucket, depth)
    {
        if (bucket.length < 32 || depth > 32) {
            mergeSort(bucket, bucket.length, stringComparator);
            for (var i = 0; i < bucket.length; ++i)
                array[dst++] = bucket[i].value;
            return dst;
        }

        var buckets = [ ];
        for (var i = 0; i < bucket.length; ++i) {
            var entry = bucket[i];
            var string = entry.string;
            if (string.length == depth) {
                array[dst++] = entry.value;
                continue;
            }

            var c = string.@charCodeAt(depth);
            if (!buckets[c])
                buckets[c] = [ ];
            buckets[c][buckets[c].length] = entry;
        }

        for (var i = 0; i < buckets.length; ++i) {
            if (!buckets[i])
                continue;
            dst = bucketSort(array, dst, buckets[i], depth + 1);
        }

        return dst;
    }

    function mergeSort(array, valueCount, comparator)
    {
        var buffer = [ ];
        buffer.length = valueCount;

        var dst = buffer;
        var src = array;
        for (var width = 1; width < valueCount; width *= 2) {
            for (var srcIndex = 0; srcIndex < valueCount; srcIndex += 2 * width)
                merge(dst, src, srcIndex, valueCount, width, comparator);

            var tmp = src;
            src = dst;
            dst = tmp;
        }

        if (src != array) {
            for(var i = 0; i < valueCount; i++)
                array[i] = src[i];
        }

    function merge(dst, src, srcIndex, srcEnd, width, comparator)
    {
        var left = srcIndex;
        var leftEnd = min(left + width, srcEnd);
        var right = leftEnd;
        var rightEnd = min(right + width, srcEnd);

        for (var dstIndex = left; dstIndex < rightEnd; ++dstIndex) {
            if (right < rightEnd) {
                if (left >= leftEnd) {
                    dst[dstIndex] = src[right++];
                    continue;
                }

                var comparisonResult = comparator(src[right], src[left]);
                if ((typeof comparisonResult === "boolean" && !comparisonResult) || comparisonResult < 0) {
                    dst[dstIndex] = src[right++];
                    continue;
                }

            }

            dst[dstIndex] = src[left++];
        }

template <typename T, typename Comparator>
MOZ_MUST_USE bool MergeSort(T* array, size_t nelems, T* scratch, Comparator c) {
  const size_t INS_SORT_LIMIT = 3;

  if (nelems <= 1) {
    return true;
  }

  /*
   * Apply insertion sort to small chunks to reduce the number of merge
   * passes needed.
   */
  for (size_t lo = 0; lo < nelems; lo += INS_SORT_LIMIT) {
    size_t hi = lo + INS_SORT_LIMIT;
    if (hi >= nelems) {
      hi = nelems;
    }
    for (size_t i = lo + 1; i != hi; i++) {
      for (size_t j = i;;) {
        bool lessOrEqual;
        if (!c(array[j - 1], array[j], &lessOrEqual)) {
          return false;
        }
        if (lessOrEqual) {
          break;
        }
        T tmp = array[j - 1];
        array[j - 1] = array[j];
        array[j] = tmp;
        if (--j == lo) {
          break;
        }
      }
    }
  }

  T* vec1 = array;
  T* vec2 = scratch;
  for (size_t run = INS_SORT_LIMIT; run < nelems; run *= 2) {
    for (size_t lo = 0; lo < nelems; lo += 2 * run) {
      size_t hi = lo + run;
      if (hi >= nelems) {
        detail::CopyNonEmptyArray(vec2 + lo, vec1 + lo, nelems - lo);
        break;
      }
      size_t run2 = (run <= nelems - hi) ? run : nelems - hi;
      if (!detail::MergeArrayRuns(vec2 + lo, vec1 + lo, run, run2, c)) {
        return false;
      }
    }
    T* swap = vec1;
    vec1 = vec2;
    vec2 = swap;
  }
  if (vec1 == scratch) {
    detail::CopyNonEmptyArray(array, scratch, nelems);
  }
  return true;
}

  transitioning macro
  ArrayTimSortImpl(context: Context, sortState: SortState, length: Smi) {
    if (length < 2) return;
    let remaining: Smi = length;

    // March over the array once, left to right, finding natural runs,
    // and extending short natural runs to minrun elements.
    let low: Smi = 0;
    const minRunLength: Smi = ComputeMinRunLength(remaining);
    while (remaining != 0) {
      let currentRunLength: Smi = CountAndMakeRun(low, low + remaining);

      // If the run is short, extend it to min(minRunLength, remaining).
      if (currentRunLength < minRunLength) {
        const forcedRunLength: Smi = SmiMin(minRunLength, remaining);
        BinaryInsertionSort(low, low + currentRunLength, low + forcedRunLength);
        currentRunLength = forcedRunLength;
      }

      // Push run onto pending-runs stack, and maybe merge.
      PushRun(sortState, low, currentRunLength);

      MergeCollapse(context, sortState);

      // Advance to find next run.
      low = low + currentRunLength;
      remaining = remaining - currentRunLength;
    }

    MergeForceCollapse(context, sortState);
    assert(GetPendingRunsSize(sortState) == 1);
    assert(GetPendingRunLength(sortState.pendingRuns, 0) == length);
  }

  // Compute a good value for the minimum run length; natural runs shorter
  // than this are boosted artificially via binary insertion sort.
  //
  // If n < 64, return n (it's too small to bother with fancy stuff).
  // Else if n is an exact power of 2, return 32.
  // Else return an int k, 32 <= k <= 64, such that n/k is close to, but
  // strictly less than, an exact power of 2.
  //
  // See listsort.txt for more info.
  macro ComputeMinRunLength(nArg: Smi): Smi {
    let n: Smi = nArg;
    let r: Smi = 0;  // Becomes 1 if any 1 bits are shifted off.

    assert(n >= 0);
    while (n >= 64) {
      r = r | (n & 1);
      n = n >> 1;
    }

    const minRunLength: Smi = n + r;
    assert(nArg < 64 || (32 <= minRunLength && minRunLength <= 64));
    return minRunLength;
  }

  // Examines the stack of runs waiting to be merged, merging adjacent runs
  // until the stack invariants are re-established:
  //
  //   1. run_length(i - 3) > run_length(i - 2) + run_length(i - 1)
  //   2. run_length(i - 2) > run_length(i - 1)
  //
  // TODO(szuend): Remove unnecessary loads. This macro was refactored to
  //               improve readability, introducing unnecessary loads in the
  //               process. Determine if all these extra loads are ok.
  transitioning macro MergeCollapse(context: Context, sortState: SortState) {
    const pendingRuns: FixedArray = sortState.pendingRuns;

    // Reload the stack size because MergeAt might change it.
    while (GetPendingRunsSize(sortState) > 1) {
      let n: Smi = GetPendingRunsSize(sortState) - 2;

      if (!RunInvariantEstablished(pendingRuns, n + 1) ||
          !RunInvariantEstablished(pendingRuns, n)) {
        if (GetPendingRunLength(pendingRuns, n - 1) <
            GetPendingRunLength(pendingRuns, n + 1)) {
          --n;
        }

        MergeAt(n);
      } else if (
          GetPendingRunLength(pendingRuns, n) <=
          GetPendingRunLength(pendingRuns, n + 1)) {
        MergeAt(n);
      } else {
        break;
      }
    }
  }

  // Merges the two runs at stack indices i and i + 1.
  // Returns kFailure if we need to bailout, kSuccess otherwise.
  transitioning builtin
  MergeAt(implicit context: Context, sortState: SortState)(i: Smi): Smi {
    const stackSize: Smi = GetPendingRunsSize(sortState);

    // We are only allowed to either merge the two top-most runs, or leave
    // the top most run alone and merge the two next runs.
    assert(stackSize >= 2);
    assert(i >= 0);
    assert(i == stackSize - 2 || i == stackSize - 3);

    const workArray = sortState.workArray;

    const pendingRuns: FixedArray = sortState.pendingRuns;
    let baseA: Smi = GetPendingRunBase(pendingRuns, i);
    let lengthA: Smi = GetPendingRunLength(pendingRuns, i);
    const baseB: Smi = GetPendingRunBase(pendingRuns, i + 1);
    let lengthB: Smi = GetPendingRunLength(pendingRuns, i + 1);
    assert(lengthA > 0 && lengthB > 0);
    assert(baseA + lengthA == baseB);

    // Record the length of the combined runs; if i is the 3rd-last run now,
    // also slide over the last run (which isn't involved in this merge).
    // The current run i + 1 goes away in any case.
    SetPendingRunLength(pendingRuns, i, lengthA + lengthB);
    if (i == stackSize - 3) {
      const base: Smi = GetPendingRunBase(pendingRuns, i + 2);
      const length: Smi = GetPendingRunLength(pendingRuns, i + 2);
      SetPendingRunBase(pendingRuns, i + 1, base);
      SetPendingRunLength(pendingRuns, i + 1, length);
    }
    sortState.pendingRunsSize = stackSize - 1;

    // Where does b start in a? Elements in a before that can be ignored,
    // because they are already in place.
    const keyRight = UnsafeCast<JSAny>(workArray.objects[baseB]);
    const k: Smi = GallopRight(workArray, keyRight, baseA, lengthA, 0);
    assert(k >= 0);

    baseA = baseA + k;
    lengthA = lengthA - k;
    if (lengthA == 0) return kSuccess;
    assert(lengthA > 0);

    // Where does a end in b? Elements in b after that can be ignored,
    // because they are already in place.
    const keyLeft = UnsafeCast<JSAny>(workArray.objects[baseA + lengthA - 1]);
    lengthB = GallopLeft(workArray, keyLeft, baseB, lengthB, lengthB - 1);
    assert(lengthB >= 0);
    if (lengthB == 0) return kSuccess;

    // Merge what remains of the runs, using a temp array with
    // min(lengthA, lengthB) elements.
    if (lengthA <= lengthB) {
      MergeLow(baseA, lengthA, baseB, lengthB);
    } else {
      MergeHigh(baseA, lengthA, baseB, lengthB);
    }
    return kSuccess;
  }