third_party/v8/builtins/array-sort.tq

// Copyright (c) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
// 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018 Python Software Foundation;
// All Rights Reserved

// This file implements a stable, adapative merge sort variant called TimSort.
//
// It was first implemented in python and this Torque implementation
// is based on the current version:
//
// https://github.com/python/cpython/blob/master/Objects/listobject.c
//
// Detailed analysis and a description of the algorithm can be found at:
//
// https://github.com/python/cpython/blob/master/Objects/listsort.txt

namespace array {
  // All accessors bail to the GenericElementsAccessor if assumptions checked
  // by "CanUseSameAccessor<>" are violated:
  //  Generic <- FastPackedSmi
  //          <- FastSmiOrObject
  //          <- FastDouble
  //          <- Dictionary
  //
  // The only exception is TempArrayElements, since it does not describe the
  // "elements" of the receiver, but instead is used as an "adaptor" so
  // GallopLeft/GallopRight can be reused with the temporary array.
  const kGenericElementsAccessorId: Smi = 0;
  const kFastElementsAccessorId: Smi = 1;

  // This is a special type, used to access the temporary array which is always
  // PACKED_ELEMENTS. As a result, we do not need a sanity check for it,
  // otherwise we might wrongly bail to the slow path.
  type TempArrayElements;

  // The following index constants describe the layout of the sortState.
  // The sortState is currently implemented as a FixedArray of
  // size kSortStateSize.

  // The receiver of the Array.p.sort call.
  const kReceiverIdx: constexpr int31 = 0;

  // The initial map and length of the receiver. After calling into JS, these
  // are reloaded and checked. If they changed we bail to the baseline
  // GenericElementsAccessor.
  const kInitialReceiverMapIdx: constexpr int31 = 1;
  const kInitialReceiverLengthIdx: constexpr int31 = 2;

  // If the user provided a comparison function, it is stored here.
  const kUserCmpFnIdx: constexpr int31 = 3;

  // Function pointer to the comparison function. This can either be a builtin
  // that calls the user-provided comparison function or "SortDefault", which
  // uses ToString and a lexicographical compare.
  const kSortComparePtrIdx: constexpr int31 = 4;

  // The following three function pointer represent a Accessor/Path.
  // These are used to Load/Store elements and to check whether to bail to the
  // baseline GenericElementsAccessor.
  const kLoadFnIdx: constexpr int31 = 5;
  const kStoreFnIdx: constexpr int31 = 6;
  const kCanUseSameAccessorFnIdx: constexpr int31 = 7;

  // If this field has the value kFailure, we need to bail to the baseline
  // GenericElementsAccessor.
  const kBailoutStatusIdx: constexpr int31 = 8;

  // This controls when we get *into* galloping mode. It's initialized to
  // kMinGallop. mergeLow and mergeHigh tend to nudge it higher for random data,
  // and lower for highly structured data.
  const kMinGallopIdx: constexpr int31 = 9;

  // A stack of sortState[kPendingRunsSizeIdx] pending runs yet to be merged.
  // Run #i starts at sortState[kPendingRunsIdx][2 * i] and extends for
  // sortState[kPendingRunsIdx][2 * i + 1] elements:
  //
  //   [..., base (i-1), length (i-1), base i, length i]
  //
  // It's always true (so long as the indices are in bounds) that
  //
  //   base of run #i + length of run #i == base of run #i + 1
  //
  const kPendingRunsSizeIdx: constexpr int31 = 10;
  const kPendingRunsIdx: constexpr int31 = 11;

  // The current size of the temporary array.
  const kTempArraySizeIdx: constexpr int31 = 12;

  // Pointer to the temporary array.
  const kTempArrayIdx: constexpr int31 = 13;

  // Contains a Smi constant describing which accessors to use. This is used
  // for reloading the right elements and for a sanity check.
  const kAccessorIdx: constexpr int31 = 14;

  const kSortStateSize: intptr = 15;

  const kFailure: Smi = -1;
  const kSuccess: Smi = 0;

  // The maximum number of entries in a SortState's pending-runs stack.
  // This is enough to sort arrays of size up to about
  //   32 * phi ** kMaxMergePending
  // where phi ~= 1.618. 85 is ridiculously large enough, good for an array with
  // 2 ** 64 elements.
  const kMaxMergePending: constexpr int31 = 85;

  // When we get into galloping mode, we stay there until both runs win less
  // often then kMinGallop consecutive times. See listsort.txt for more info.
  const kMinGallopWins: constexpr int31 = 7;

  // Default size of the temporary array. The temporary array is allocated when
  // it is first requested, but it has always at least this size.
  const kSortStateTempSize: Smi = 32;

  type LoadFn = builtin(Context, FixedArray, Smi) => Object;
  type StoreFn = builtin(Context, FixedArray, Smi, Object) => Smi;
  type CanUseSameAccessorFn = builtin(Context, JSReceiver, Object, Number) =>
      Boolean;
  type CompareBuiltinFn = builtin(Context, Object, Object, Object) => Number;

  // The following builtins implement Load/Store for all the Accessors.
  // The most generic baseline version uses Get-/SetProperty. We do not need
  // to worry about the prototype chain, because the pre-processing step has
  // copied values from the prototype chain to the receiver if they were visible
  // through a hole.

  transitioning builtin Load<ElementsAccessor: type>(
      context: Context, sortState: FixedArray, index: Smi): Object {
    const receiver = GetReceiver(sortState);
    return GetProperty(receiver, index);
  }

  Load<FastPackedSmiElements>(
      context: Context, sortState: FixedArray, index: Smi): Object {
    const receiver = GetReceiver(sortState);
    const object = UnsafeCast<JSObject>(receiver);
    const elements = UnsafeCast<FixedArray>(object.elements);
    return elements[index];
  }

  Load<FastSmiOrObjectElements>(
      context: Context, sortState: FixedArray, index: Smi): Object {
    const receiver = GetReceiver(sortState);
    const object = UnsafeCast<JSObject>(receiver);
    const elements = UnsafeCast<FixedArray>(object.elements);
    const result: Object = elements[index];
    if (IsTheHole(result)) {
      // The pre-processing step removed all holes by compacting all elements
      // at the start of the array. Finding a hole means the cmp function or
      // ToString changes the array.
      return Failure(sortState);
    }
    return result;
  }

  Load<FastDoubleElements>(context: Context, sortState: FixedArray, index: Smi):
      Object {
    try {
      const receiver = GetReceiver(sortState);
      const object = UnsafeCast<JSObject>(receiver);
      const elements = UnsafeCast<FixedDoubleArray>(object.elements);
      const value = LoadDoubleWithHoleCheck(elements, index) otherwise Bailout;
      return AllocateHeapNumberWithValue(value);
    }
    label Bailout {
      // The pre-processing step removed all holes by compacting all elements
      // at the start of the array. Finding a hole means the cmp function or
      // ToString changes the array.
      return Failure(sortState);
    }
  }

  Load<DictionaryElements>(context: Context, sortState: FixedArray, index: Smi):
      Object {
    try {
      const receiver = GetReceiver(sortState);
      const object = UnsafeCast<JSObject>(receiver);
      const dictionary = UnsafeCast<NumberDictionary>(object.elements);
      const intptrIndex = Convert<intptr>(index);
      return BasicLoadNumberDictionaryElement(dictionary, intptrIndex)
          otherwise Bailout, Bailout;
    }
    label Bailout {
      return Failure(sortState);
    }
  }

  Load<TempArrayElements>(context: Context, sortState: FixedArray, index: Smi):
      Object {
    const elements = GetTempArray(sortState);
    assert(IsFixedArray(elements));
    return elements[index];
  }

  transitioning builtin Store<ElementsAccessor: type>(
      context: Context, sortState: FixedArray, index: Smi, value: Object): Smi {
    const receiver = GetReceiver(sortState);
    SetProperty(receiver, index, value);
    return kSuccess;
  }

  Store<FastPackedSmiElements>(
      context: Context, sortState: FixedArray, index: Smi, value: Object): Smi {
    const receiver = GetReceiver(sortState);
    const object = UnsafeCast<JSObject>(receiver);
    const elements = UnsafeCast<FixedArray>(object.elements);
    StoreFixedArrayElementSmi(elements, index, value, SKIP_WRITE_BARRIER);
    return kSuccess;
  }

  Store<FastSmiOrObjectElements>(
      context: Context, sortState: FixedArray, index: Smi, value: Object): Smi {
    const receiver = GetReceiver(sortState);
    const object = UnsafeCast<JSObject>(receiver);
    const elements = UnsafeCast<FixedArray>(object.elements);
    elements[index] = value;
    return kSuccess;
  }

  Store<FastDoubleElements>(
      context: Context, sortState: FixedArray, index: Smi, value: Object): Smi {
    const receiver = GetReceiver(sortState);
    const object = UnsafeCast<JSObject>(receiver);
    const elements = UnsafeCast<FixedDoubleArray>(object.elements);
    const heapVal = UnsafeCast<HeapNumber>(value);
    // Make sure we do not store signalling NaNs into double arrays.
    const val = Float64SilenceNaN(Convert<float64>(heapVal));
    StoreFixedDoubleArrayElementWithSmiIndex(elements, index, val);
    return kSuccess;
  }

  Store<DictionaryElements>(
      context: Context, sortState: FixedArray, index: Smi, value: Object): Smi {
    const receiver = GetReceiver(sortState);
    const object = UnsafeCast<JSObject>(receiver);
    const dictionary = UnsafeCast<NumberDictionary>(object.elements);
    const intptrIndex = Convert<intptr>(index);
    try {
      BasicStoreNumberDictionaryElement(dictionary, intptrIndex, value)
          otherwise Fail, Fail, ReadOnly;
      return kSuccess;
    }
    label ReadOnly {
      // We cannot write to read-only data properties. Throw the same TypeError
      // as SetProperty would.
      const receiver = GetReceiver(sortState);
      ThrowTypeError(
          context, kStrictReadOnlyProperty, index, Typeof(receiver), receiver);
    }
    label Fail {
      return Failure(sortState);
    }
  }

  Store<TempArrayElements>(
      context: Context, sortState: FixedArray, index: Smi, value: Object): Smi {
    const elements = GetTempArray(sortState);
    elements[index] = value;
    return kSuccess;
  }

  UnsafeCast<CompareBuiltinFn>(implicit context: Context)(o: Object):
      CompareBuiltinFn {
    return %RawDownCast<CompareBuiltinFn>(o);
  }
  UnsafeCast<LoadFn>(implicit context: Context)(o: Object): LoadFn {
    return %RawDownCast<LoadFn>(o);
  }
  UnsafeCast<StoreFn>(implicit context: Context)(o: Object): StoreFn {
    return %RawDownCast<StoreFn>(o);
  }
  UnsafeCast<CanUseSameAccessorFn>(implicit context: Context)(o: Object):
      CanUseSameAccessorFn {
    return %RawDownCast<CanUseSameAccessorFn>(o);
  }

  builtin SortCompareDefault(
      context: Context, comparefn: Object, x: Object, y: Object): Number {
    assert(comparefn == Undefined);

    if (TaggedIsSmi(x) && TaggedIsSmi(y)) {
      return SmiLexicographicCompare(UnsafeCast<Smi>(x), UnsafeCast<Smi>(y));
    }

    // 5. Let xString be ? ToString(x).
    const xString = ToString_Inline(context, x);

    // 6. Let yString be ? ToString(y).
    const yString = ToString_Inline(context, y);

    // 7. Let xSmaller be the result of performing
    //    Abstract Relational Comparison xString < yString.
    // 8. If xSmaller is true, return -1.
    if (StringLessThan(context, xString, yString) == True) return -1;

    // 9. Let ySmaller be the result of performing
    //    Abstract Relational Comparison yString < xString.
    // 10. If ySmaller is true, return 1.
    if (StringLessThan(context, yString, xString) == True) return 1;

    // 11. Return +0.
    return 0;
  }

  transitioning builtin SortCompareUserFn(
      context: Context, comparefn: Object, x: Object, y: Object): Number {
    assert(comparefn != Undefined);
    const cmpfn = UnsafeCast<Callable>(comparefn);

    // a. Let v be ? ToNumber(? Call(comparefn, undefined, x, y)).
    const v = ToNumber_Inline(context, Call(context, cmpfn, Undefined, x, y));

    // b. If v is NaN, return +0.
    if (NumberIsNaN(v)) return 0;

    // c. return v.
    return v;
  }

  builtin CanUseSameAccessor<ElementsAccessor: type>(
      context: Context, receiver: JSReceiver, initialReceiverMap: Object,
      initialReceiverLength: Number): Boolean {
    const a: JSArray = UnsafeCast<JSArray>(receiver);
    if (a.map != initialReceiverMap) return False;

    assert(TaggedIsSmi(initialReceiverLength));
    let originalLength: Smi = UnsafeCast<Smi>(initialReceiverLength);
    if (UnsafeCast<Smi>(a.length) != originalLength) return False;

    return True;
  }

  CanUseSameAccessor<GenericElementsAccessor>(
      context: Context, receiver: JSReceiver, initialReceiverMap: Object,
      initialReceiverLength: Number): Boolean {
    // Do nothing. We are already on the slow path.
    return True;
  }

  CanUseSameAccessor<DictionaryElements>(
      context: Context, receiver: JSReceiver, initialReceiverMap: Object,
      initialReceiverLength: Number): Boolean {
    let obj: JSReceiver = UnsafeCast<JSReceiver>(receiver);
    return SelectBooleanConstant(obj.map == initialReceiverMap);
  }

  macro CallCompareFn(
      context: Context, sortState: FixedArray, x: Object, y: Object): Number
      labels Bailout {
    const userCmpFn: Object = sortState[kUserCmpFnIdx];
    const sortCompare: CompareBuiltinFn =
        UnsafeCast<CompareBuiltinFn>(sortState[kSortComparePtrIdx]);

    const result: Number = sortCompare(context, userCmpFn, x, y);

    const receiver: JSReceiver = GetReceiver(sortState);
    const initialReceiverMap: Object = sortState[kInitialReceiverMapIdx];
    const initialReceiverLength: Number = GetInitialReceiverLength(sortState);
    const canUseSameAccessorFn: CanUseSameAccessorFn =
        GetCanUseSameAccessorFn(sortState);

    if (!canUseSameAccessorFn(
            context, receiver, initialReceiverMap, initialReceiverLength)) {
      goto Bailout;
    }
    return result;
  }

  macro GetInitialReceiverLength(implicit context:
                                     Context)(sortState: FixedArray): Number {
    return UnsafeCast<Number>(sortState[kInitialReceiverLengthIdx]);
  }

  macro GetLoadFn(implicit context: Context)(sortState: FixedArray): LoadFn {
    return UnsafeCast<LoadFn>(sortState[kLoadFnIdx]);
  }

  macro GetStoreFn(implicit context: Context)(sortState: FixedArray): StoreFn {
    return UnsafeCast<StoreFn>(sortState[kStoreFnIdx]);
  }

  macro GetCanUseSameAccessorFn(implicit context: Context)(
      sortState: FixedArray): CanUseSameAccessorFn {
    return UnsafeCast<CanUseSameAccessorFn>(
        sortState[kCanUseSameAccessorFnIdx]);
  }

  macro GetReceiver(implicit context: Context)(sortState: FixedArray):
      JSReceiver {
    return UnsafeCast<JSReceiver>(sortState[kReceiverIdx]);
  }

  // Returns the temporary array without changing its size.
  macro GetTempArray(implicit context: Context)(sortState: FixedArray):
      FixedArray {
    return UnsafeCast<FixedArray>(sortState[kTempArrayIdx]);
  }

  // Re-loading the stack-size is done in a few places. The small macro allows
  // for easier invariant checks at all use sites.
  macro GetPendingRunsSize(implicit context: Context)(sortState: FixedArray):
      Smi {
    assert(TaggedIsSmi(sortState[kPendingRunsSizeIdx]));
    const stackSize: Smi = UnsafeCast<Smi>(sortState[kPendingRunsSizeIdx]);

    assert(stackSize >= 0);
    return stackSize;
  }

  macro SetPendingRunsSize(sortState: FixedArray, value: Smi) {
    sortState[kPendingRunsSizeIdx] = value;
  }

  macro GetPendingRunBase(implicit context:
                              Context)(pendingRuns: FixedArray, run: Smi): Smi {
    return UnsafeCast<Smi>(pendingRuns[run << 1]);
  }

  macro SetPendingRunBase(pendingRuns: FixedArray, run: Smi, value: Smi) {
    pendingRuns[run << 1] = value;
  }

  macro GetPendingRunLength(implicit context: Context)(
      pendingRuns: FixedArray, run: Smi): Smi {
    return UnsafeCast<Smi>(pendingRuns[(run << 1) + 1]);
  }

  macro SetPendingRunLength(pendingRuns: FixedArray, run: Smi, value: Smi) {
    pendingRuns[(run << 1) + 1] = value;
  }

  macro PushRun(implicit context:
                    Context)(sortState: FixedArray, base: Smi, length: Smi) {
    assert(GetPendingRunsSize(sortState) < kMaxMergePending);

    const stackSize: Smi = GetPendingRunsSize(sortState);
    const pendingRuns: FixedArray =
        UnsafeCast<FixedArray>(sortState[kPendingRunsIdx]);

    SetPendingRunBase(pendingRuns, stackSize, base);
    SetPendingRunLength(pendingRuns, stackSize, length);

    SetPendingRunsSize(sortState, stackSize + 1);
  }

  // Returns the temporary array and makes sure that it is big enough.
  // TODO(szuend): Implement a better re-size strategy.
  macro GetTempArray(implicit context: Context)(
      sortState: FixedArray, requestedSize: Smi): FixedArray {
    const minSize: Smi = SmiMax(kSortStateTempSize, requestedSize);

    const currentSize: Smi = UnsafeCast<Smi>(sortState[kTempArraySizeIdx]);
    if (currentSize >= minSize) {
      return GetTempArray(sortState);
    }

    const tempArray: FixedArray =
        AllocateZeroedFixedArray(Convert<intptr>(minSize));

    sortState[kTempArraySizeIdx] = minSize;
    sortState[kTempArrayIdx] = tempArray;
    return tempArray;
  }

  // This macro jumps to the Bailout label iff kBailoutStatus is kFailure.
  macro EnsureSuccess(implicit context:
                          Context)(sortState: FixedArray) labels Bailout {
    const status: Smi = UnsafeCast<Smi>(sortState[kBailoutStatusIdx]);
    if (status == kFailure) goto Bailout;
  }

  // Sets kBailoutStatus to kFailure and returns kFailure.
  macro Failure(sortState: FixedArray): Smi {
    sortState[kBailoutStatusIdx] = kFailure;
    return kFailure;
  }

  // The following Call* macros wrap builtin calls, making call sites more
  // readable since we can use labels and do not have to check kBailoutStatus
  // or the return value.

  macro CallLoad(
      context: Context, sortState: FixedArray, load: LoadFn, index: Smi): Object
      labels Bailout {
    const result: Object = load(context, sortState, index);
    EnsureSuccess(sortState) otherwise Bailout;
    return result;
  }

  macro CallStore(
      context: Context, sortState: FixedArray, store: StoreFn, index: Smi,
      value: Object) labels Bailout {
    store(context, sortState, index, value);
    EnsureSuccess(sortState) otherwise Bailout;
  }

  transitioning macro CallCopyFromTempArray(
      context: Context, sortState: FixedArray, dstPos: Smi, srcPos: Smi,
      length: Smi)
      labels Bailout {
    CopyFromTempArray(context, sortState, dstPos, srcPos, length);
    EnsureSuccess(sortState) otherwise Bailout;
  }

  transitioning macro CallCopyWithinSortArray(
      context: Context, sortState: FixedArray, srcPos: Smi, dstPos: Smi,
      length: Smi)
      labels Bailout {
    CopyWithinSortArray(context, sortState, srcPos, dstPos, length);
    EnsureSuccess(sortState) otherwise Bailout;
  }

  macro CallGallopRight(
      context: Context, sortState: FixedArray, load: LoadFn, key: Object,
      base: Smi, length: Smi, hint: Smi): Smi
      labels Bailout {
    const result: Smi =
        GallopRight(context, sortState, load, key, base, length, hint);
    EnsureSuccess(sortState) otherwise Bailout;
    return result;
  }

  macro CallGallopLeft(
      context: Context, sortState: FixedArray, load: LoadFn, key: Object,
      base: Smi, length: Smi, hint: Smi): Smi
      labels Bailout {
    const result: Smi =
        GallopLeft(context, sortState, load, key, base, length, hint);
    EnsureSuccess(sortState) otherwise Bailout;
    return result;
  }

  transitioning macro
  CallMergeAt(context: Context, sortState: FixedArray, i: Smi)
      labels Bailout {
    MergeAt(context, sortState, i);
    EnsureSuccess(sortState) otherwise Bailout;
  }

  transitioning macro CopyToTempArray(
      context: Context, sortState: FixedArray, load: LoadFn, srcPos: Smi,
      tempArray: FixedArray, dstPos: Smi, length: Smi)
      labels Bailout {
    assert(srcPos >= 0);
    assert(dstPos >= 0);
    assert(srcPos <= GetInitialReceiverLength(sortState) - length);
    assert(dstPos <= tempArray.length - length);

    let srcIdx: Smi = srcPos;
    let dstIdx: Smi = dstPos;
    let to: Smi = srcPos + length;

    while (srcIdx < to) {
      let element: Object = CallLoad(context, sortState, load, srcIdx++)
          otherwise Bailout;
      tempArray[dstIdx++] = element;
    }
  }

  transitioning builtin CopyFromTempArray(
      context: Context, sortState: FixedArray, dstPos: Smi, srcPos: Smi,
      length: Smi): Smi {
    const tempArray = GetTempArray(sortState);
    assert(srcPos >= 0);
    assert(dstPos >= 0);
    assert(srcPos <= tempArray.length - length);
    assert(dstPos <= GetInitialReceiverLength(sortState) - length);

    let store: StoreFn = GetStoreFn(sortState);

    let srcIdx: Smi = srcPos;
    let dstIdx: Smi = dstPos;
    let to: Smi = srcPos + length;
    try {
      while (srcIdx < to) {
        CallStore(context, sortState, store, dstIdx++, tempArray[srcIdx++])
            otherwise Bailout;
      }
      return kSuccess;
    }
    label Bailout {
      return Failure(sortState);
    }
  }

  transitioning builtin CopyWithinSortArray(
      context: Context, sortState: FixedArray, srcPos: Smi, dstPos: Smi,
      length: Smi): Smi {
    assert(srcPos >= 0);
    assert(dstPos >= 0);
    assert(srcPos <= GetInitialReceiverLength(sortState) - length);
    assert(dstPos <= GetInitialReceiverLength(sortState) - length);

    try {
      let load: LoadFn = GetLoadFn(sortState);
      let store: StoreFn = GetStoreFn(sortState);

      if (srcPos < dstPos) {
        let srcIdx: Smi = srcPos + length - 1;
        let dstIdx: Smi = dstPos + length - 1;
        while (srcIdx >= srcPos) {
          CopyElement(context, sortState, load, store, srcIdx--, dstIdx--)
              otherwise Bailout;
        }
      } else {
        let srcIdx: Smi = srcPos;
        let dstIdx: Smi = dstPos;
        let to: Smi = srcPos + length;
        while (srcIdx < to) {
          CopyElement(context, sortState, load, store, srcIdx++, dstIdx++)
              otherwise Bailout;
        }
      }
      return kSuccess;
    }
    label Bailout {
      return Failure(sortState);
    }
  }

  // BinaryInsertionSort is the best method for sorting small arrays: it does
  // few compares, but can do data movement quadratic in the number of elements.
  // This is an advantage since comparisons are more expensive due to
  // calling into JS.
  //
  //  [low, high) is a contiguous range of a array, and is sorted via
  // binary insertion. This sort is stable.
  //
  // On entry, must have low <= start <= high, and that [low, start) is already
  // sorted. Pass start == low if you do not know!.
  builtin BinaryInsertionSort(
      context: Context, sortState: FixedArray, low: Smi, startArg: Smi,
      high: Smi): Smi {
    assert(low <= startArg && startArg <= high);

    try {
      const load: LoadFn = GetLoadFn(sortState);
      const store: StoreFn = GetStoreFn(sortState);

      let start: Smi = low == startArg ? (startArg + 1) : startArg;

      for (; start < high; ++start) {
        // Set left to where a[start] belongs.
        let left: Smi = low;
        let right: Smi = start;

        const pivot: Object = CallLoad(context, sortState, load, right)
            otherwise Bailout;

        // Invariants:
        //   pivot >= all in [low, left).
        //   pivot  < all in [right, start).
        assert(left < right);

        // Find pivot insertion point.
        while (left < right) {
          const mid: Smi = left + ((right - left) >> 1);
          const midElement: Object = CallLoad(context, sortState, load, mid)
              otherwise Bailout;
          const order: Number =
              CallCompareFn(context, sortState, pivot, midElement)
              otherwise Bailout;

          if (order < 0) {
            right = mid;
          } else {
            left = mid + 1;
          }
        }
        assert(left == right);

        // The invariants still hold, so:
        //   pivot >= all in [low, left) and
        //   pivot  < all in [left, start),
        //
        // so pivot belongs at left. Note that if there are elements equal to
        // pivot, left points to the first slot after them -- that's why this
        // sort is stable.
        // Slide over to make room.
        for (let p: Smi = start; p > left; --p) {
          CopyElement(context, sortState, load, store, p - 1, p)
              otherwise Bailout;
        }
        CallStore(context, sortState, store, left, pivot)
            otherwise Bailout;
      }
      return kSuccess;
    }
    label Bailout {
      return Failure(sortState);
    }
  }

  // Return the length of the run beginning at low, in the range [low, high),
  // low < high is required on entry.
  // "A run" is the longest ascending sequence, with
  //
  //   a[low] <= a[low + 1] <= a[low + 2] <= ...
  //
  // or the longest descending sequence, with
  //
  //   a[low] > a[low + 1] > a[low + 2] > ...
  //
  // For its intended use in stable mergesort, the strictness of the definition
  // of "descending" is needed so that the range can safely be reversed
  // without violating stability (strict ">" ensures there are no equal
  // elements to get out of order).
  //
  // In addition, if the run is "descending", it is reversed, so the returned
  // length is always an ascending sequence.
  macro CountAndMakeRun(
      context: Context, sortState: FixedArray, lowArg: Smi, high: Smi): Smi
      labels Bailout {
    assert(lowArg < high);

    const load: LoadFn = GetLoadFn(sortState);
    const store: StoreFn = GetStoreFn(sortState);

    let low: Smi = lowArg + 1;
    if (low == high) return 1;

    let runLength: Smi = 2;

    const elementLow: Object =
        CallLoad(context, sortState, load, low) otherwise Bailout;
    const elementLowPred: Object =
        CallLoad(context, sortState, load, low - 1) otherwise Bailout;
    let order: Number =
        CallCompareFn(context, sortState, elementLow, elementLowPred)
        otherwise Bailout;

    // TODO(szuend): Replace with "order < 0" once Torque supports it.
    //               Currently the operator<(Number, Number) has return type
    //               'never' and uses two labels to branch.
    const isDescending: bool = order < 0 ? true : false;

    let previousElement: Object = elementLow;
    for (let idx: Smi = low + 1; idx < high; ++idx) {
      const currentElement: Object =
          CallLoad(context, sortState, load, idx) otherwise Bailout;
      order = CallCompareFn(context, sortState, currentElement, previousElement)
          otherwise Bailout;

      if (isDescending) {
        if (order >= 0) break;
      } else {
        if (order < 0) break;
      }

      previousElement = currentElement;
      ++runLength;
    }

    if (isDescending) {
      ReverseRange(context, sortState, load, store, lowArg, lowArg + runLength)
          otherwise Bailout;
    }

    return runLength;
  }

  macro ReverseRange(
      context: Context, sortState: FixedArray, load: LoadFn, store: StoreFn,
      from: Smi, to: Smi)
      labels Bailout {
    let low: Smi = from;
    let high: Smi = to - 1;

    while (low < high) {
      const elementLow: Object =
          CallLoad(context, sortState, load, low) otherwise Bailout;
      const elementHigh: Object =
          CallLoad(context, sortState, load, high) otherwise Bailout;
      CallStore(context, sortState, store, low++, elementHigh)
          otherwise Bailout;
      CallStore(context, sortState, store, high--, elementLow)
          otherwise Bailout;
    }
  }

  // Merges the two runs at stack indices i and i + 1.
  // Returns kFailure if we need to bailout, kSuccess otherwise.
  transitioning builtin
  MergeAt(context: Context, sortState: FixedArray, 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 load: LoadFn = GetLoadFn(sortState);

    const pendingRuns: FixedArray =
        UnsafeCast<FixedArray>(sortState[kPendingRunsIdx]);
    let baseA: Smi = GetPendingRunBase(pendingRuns, i);
    let lengthA: Smi = GetPendingRunLength(pendingRuns, i);
    let 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);
    }
    SetPendingRunsSize(sortState, stackSize - 1);

    try {
      // Where does b start in a? Elements in a before that can be ignored,
      // because they are already in place.
      const keyRight: Object = CallLoad(context, sortState, load, baseB)
          otherwise Bailout;
      const k: Smi =
          CallGallopRight(context, sortState, load, keyRight, baseA, lengthA, 0)
          otherwise Bailout;
      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.
      let keyLeft: Object =
          CallLoad(context, sortState, load, baseA + lengthA - 1)
          otherwise Bailout;
      lengthB = CallGallopLeft(
          context, sortState, load, keyLeft, baseB, lengthB, lengthB - 1)
          otherwise Bailout;
      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(context, sortState, baseA, lengthA, baseB, lengthB)
            otherwise Bailout;
      } else {
        MergeHigh(context, sortState, baseA, lengthA, baseB, lengthB)
            otherwise Bailout;
      }
      return kSuccess;
    }
    label Bailout {
      return Failure(sortState);
    }
  }

  // Locates the proper position of key in a sorted array; if the array contains
  // an element equal to key, return the position immediately to the left of
  // the leftmost equal element. (GallopRight does the same except returns the
  // position to the right of the rightmost equal element (if any)).
  //
  // The array is sorted with "length" elements, starting at "base".
  // "length" must be > 0.
  //
  // "hint" is an index at which to begin the search, 0 <= hint < n. The closer
  // hint is to the final result, the faster this runs.
  //
  // The return value is the int offset in 0..length such that
  //
  // array[base + offset] < key <= array[base + offset + 1]
  //
  // pretending that array[base - 1] is minus infinity and array[base + len]
  // is plus infinity. In other words, key belongs at index base + k.
  builtin GallopLeft(
      context: Context, sortState: FixedArray, load: LoadFn, key: Object,
      base: Smi, length: Smi, hint: Smi): Smi {
    assert(length > 0 && base >= 0);
    assert(0 <= hint && hint < length);

    let lastOfs: Smi = 0;
    let offset: Smi = 1;

    try {
      const baseHintElement: Object =
          CallLoad(context, sortState, load, base + hint)
          otherwise Bailout;
      let order: Number =
          CallCompareFn(context, sortState, baseHintElement, key)
          otherwise Bailout;

      if (order < 0) {
        // a[base + hint] < key: gallop right, until
        // a[base + hint + lastOfs] < key <= a[base + hint + offset].

        // a[base + length - 1] is highest.
        let maxOfs: Smi = length - hint;
        while (offset < maxOfs) {
          const offsetElement: Object =
              CallLoad(context, sortState, load, base + hint + offset)
              otherwise Bailout;
          order = CallCompareFn(context, sortState, offsetElement, key)
              otherwise Bailout;

          // a[base + hint + offset] >= key? Break.
          if (order >= 0) break;

          lastOfs = offset;
          offset = (offset << 1) + 1;

          // Integer overflow.
          if (offset <= 0) offset = maxOfs;
        }

        if (offset > maxOfs) offset = maxOfs;

        // Translate back to positive offsets relative to base.
        lastOfs = lastOfs + hint;
        offset = offset + hint;
      } else {
        // key <= a[base + hint]: gallop left, until
        // a[base + hint - offset] < key <= a[base + hint - lastOfs].
        assert(order >= 0);

        // a[base + hint] is lowest.
        let maxOfs: Smi = hint + 1;
        while (offset < maxOfs) {
          const offsetElement: Object =
              CallLoad(context, sortState, load, base + hint - offset)
              otherwise Bailout;
          order = CallCompareFn(context, sortState, offsetElement, key)
              otherwise Bailout;

          if (order < 0) break;

          lastOfs = offset;
          offset = (offset << 1) + 1;

          // Integer overflow.
          if (offset <= 0) offset = maxOfs;
        }

        if (offset > maxOfs) offset = maxOfs;

        // Translate back to positive offsets relative to base.
        const tmp: Smi = lastOfs;
        lastOfs = hint - offset;
        offset = hint - tmp;
      }

      assert(-1 <= lastOfs && lastOfs < offset && offset <= length);

      // Now a[base+lastOfs] < key <= a[base+offset], so key belongs somewhere
      // to the right of lastOfs but no farther right than offset. Do a binary
      // search, with invariant:
      //   a[base + lastOfs - 1] < key <= a[base + offset].
      lastOfs++;
      while (lastOfs < offset) {
        const m: Smi = lastOfs + ((offset - lastOfs) >> 1);

        const baseMElement: Object =
            CallLoad(context, sortState, load, base + m)
            otherwise Bailout;
        order = CallCompareFn(context, sortState, baseMElement, key)
            otherwise Bailout;

        if (order < 0) {
          lastOfs = m + 1;  // a[base + m] < key.
        } else {
          offset = m;  // key <= a[base + m].
        }
      }
      // so a[base + offset - 1] < key <= a[base + offset].
      assert(lastOfs == offset);
      assert(0 <= offset && offset <= length);
      return offset;
    }
    label Bailout {
      return Failure(sortState);
    }
  }

  // Exactly like GallopLeft, except that if key already exists in
  // [base, base + length), finds the position immediately to the right of the
  // rightmost equal value.
  //
  // The return value is the int offset in 0..length such that
  //
  // array[base + offset - 1] <= key < array[base + offset]
  //
  // or kFailure on error.
  builtin GallopRight(
      context: Context, sortState: FixedArray, load: LoadFn, key: Object,
      base: Smi, length: Smi, hint: Smi): Smi {
    assert(length > 0 && base >= 0);
    assert(0 <= hint && hint < length);

    let lastOfs: Smi = 0;
    let offset: Smi = 1;

    try {
      const baseHintElement: Object =
          CallLoad(context, sortState, load, base + hint)
          otherwise Bailout;
      let order: Number =
          CallCompareFn(context, sortState, key, baseHintElement)
          otherwise Bailout;

      if (order < 0) {
        // key < a[base + hint]: gallop left, until
        // a[base + hint - offset] <= key < a[base + hint - lastOfs].

        // a[base + hint] is lowest.
        let maxOfs: Smi = hint + 1;
        while (offset < maxOfs) {
          const offsetElement: Object =
              CallLoad(context, sortState, load, base + hint - offset)
              otherwise Bailout;
          order = CallCompareFn(context, sortState, key, offsetElement)
              otherwise Bailout;

          if (order >= 0) break;

          lastOfs = offset;
          offset = (offset << 1) + 1;

          // Integer overflow.
          if (offset <= 0) offset = maxOfs;
        }

        if (offset > maxOfs) offset = maxOfs;

        // Translate back to positive offsets relative to base.
        const tmp: Smi = lastOfs;
        lastOfs = hint - offset;
        offset = hint - tmp;
      } else {
        // a[base + hint] <= key: gallop right, until
        // a[base + hint + lastOfs] <= key < a[base + hint + offset].

        // a[base + length - 1] is highest.
        let maxOfs: Smi = length - hint;
        while (offset < maxOfs) {
          const offsetElement: Object =
              CallLoad(context, sortState, load, base + hint + offset)
              otherwise Bailout;
          order = CallCompareFn(context, sortState, key, offsetElement)
              otherwise Bailout;

          // a[base + hint + ofs] <= key.
          if (order < 0) break;

          lastOfs = offset;
          offset = (offset << 1) + 1;

          // Integer overflow.
          if (offset <= 0) offset = maxOfs;
        }

        if (offset > maxOfs) offset = maxOfs;

        // Translate back to positive offests relative to base.
        lastOfs = lastOfs + hint;
        offset = offset + hint;
      }
      assert(-1 <= lastOfs && lastOfs < offset && offset <= length);

      // Now a[base + lastOfs] <= key < a[base + ofs], so key belongs
      // somewhere to the right of lastOfs but no farther right than ofs.
      // Do a binary search, with invariant
      // a[base + lastOfs - 1] < key <= a[base + ofs].
      lastOfs++;
      while (lastOfs < offset) {
        const m: Smi = lastOfs + ((offset - lastOfs) >> 1);

        const baseMElement: Object =
            CallLoad(context, sortState, load, base + m)
            otherwise Bailout;
        order = CallCompareFn(context, sortState, key, baseMElement)
            otherwise Bailout;

        if (order < 0) {
          offset = m;  // key < a[base + m].
        } else {
          lastOfs = m + 1;  // a[base + m] <= key.
        }
      }
      // so a[base + offset - 1] <= key < a[base + offset].
      assert(lastOfs == offset);
      assert(0 <= offset && offset <= length);
      return offset;
    }
    label Bailout {
      return Failure(sortState);
    }
  }

  // Copies a single element inside the array/object (NOT the tempArray).
  macro CopyElement(
      context: Context, sortState: FixedArray, load: LoadFn, store: StoreFn,
      from: Smi, to: Smi)
      labels Bailout {
    const element: Object = CallLoad(context, sortState, load, from)
        otherwise Bailout;
    CallStore(context, sortState, store, to, element)
        otherwise Bailout;
  }

  // Merge the lengthA elements starting at baseA with the lengthB elements
  // starting at baseB in a stable way, in-place. lengthA and lengthB must
  // be > 0, and baseA + lengthA == baseB. Must also have that
  // array[baseB] < array[baseA],
  // that array[baseA + lengthA - 1] belongs at the end of the merge,
  // and should have lengthA <= lengthB.
  transitioning macro MergeLow(
      context: Context, sortState: FixedArray, baseA: Smi, lengthAArg: Smi,
      baseB: Smi, lengthBArg: Smi)
      labels Bailout {
    assert(0 < lengthAArg && 0 < lengthBArg);
    assert(0 <= baseA && 0 < baseB);
    assert(baseA + lengthAArg == baseB);

    let lengthA: Smi = lengthAArg;
    let lengthB: Smi = lengthBArg;

    const load: LoadFn = GetLoadFn(sortState);
    const store: StoreFn = GetStoreFn(sortState);

    const tempArray: FixedArray = GetTempArray(sortState, lengthA);
    CopyToTempArray(context, sortState, load, baseA, tempArray, 0, lengthA)
        otherwise Bailout;

    let dest: Smi = baseA;
    let cursorTemp: Smi = 0;
    let cursorB: Smi = baseB;

    CopyElement(context, sortState, load, store, cursorB++, dest++)
        otherwise Bailout;

    try {
      if (--lengthB == 0) goto Succeed;
      if (lengthA == 1) goto CopyB;

      let minGallop: Smi = UnsafeCast<Smi>(sortState[kMinGallopIdx]);
      // TODO(szuend): Replace with something that does not have a runtime
      //               overhead as soon as its available in Torque.
      while (Int32TrueConstant()) {
        let nofWinsA: Smi = 0;  // # of times A won in a row.
        let nofWinsB: Smi = 0;  // # of times B won in a row.

        // Do the straightforward thing until (if ever) one run appears to
        // win consistently.
        // TODO(szuend): Replace with something that does not have a runtime
        //               overhead as soon as its available in Torque.
        while (Int32TrueConstant()) {
          assert(lengthA > 1 && lengthB > 0);

          let elementB: Object = CallLoad(context, sortState, load, cursorB)
              otherwise Bailout;
          let order: Number =
              CallCompareFn(context, sortState, elementB, tempArray[cursorTemp])
              otherwise Bailout;

          if (order < 0) {
            CopyElement(context, sortState, load, store, cursorB, dest)
                otherwise Bailout;

            ++cursorB;
            ++dest;
            ++nofWinsB;
            --lengthB;
            nofWinsA = 0;

            if (lengthB == 0) goto Succeed;
            if (nofWinsB >= minGallop) break;
          } else {
            CallStore(context, sortState, store, dest, tempArray[cursorTemp])
                otherwise Bailout;

            ++cursorTemp;
            ++dest;
            ++nofWinsA;
            --lengthA;
            nofWinsB = 0;

            if (lengthA == 1) goto CopyB;
            if (nofWinsA >= minGallop) break;
          }
        }

        // One run is winning so consistently that galloping may be a huge win.
        // So try that, and continue galloping until (if ever) neither run
        // appears to be winning consistently anymore.
        ++minGallop;
        let firstIteration: bool = true;
        while (nofWinsA >= kMinGallopWins || nofWinsB >= kMinGallopWins ||
               firstIteration) {
          firstIteration = false;
          assert(lengthA > 1 && lengthB > 0);

          minGallop = SmiMax(1, minGallop - 1);
          sortState[kMinGallopIdx] = minGallop;

          let keyRight: Object = CallLoad(context, sortState, load, cursorB)
              otherwise Bailout;
          nofWinsA = CallGallopRight(
              context, sortState, Load<TempArrayElements>, keyRight, cursorTemp,
              lengthA, 0) otherwise Bailout;
          assert(nofWinsA >= 0);

          if (nofWinsA > 0) {
            CallCopyFromTempArray(
                context, sortState, dest, cursorTemp, nofWinsA)
                otherwise Bailout;
            dest = dest + nofWinsA;
            cursorTemp = cursorTemp + nofWinsA;
            lengthA = lengthA - nofWinsA;

            if (lengthA == 1) goto CopyB;

            // lengthA == 0 is impossible now if the comparison function is
            // consistent, but we can't assume that it is.
            if (lengthA == 0) goto Succeed;
          }
          CopyElement(context, sortState, load, store, cursorB++, dest++)
              otherwise Bailout;
          if (--lengthB == 0) goto Succeed;

          nofWinsB = CallGallopLeft(
              context, sortState, load, tempArray[cursorTemp], cursorB, lengthB,
              0)
              otherwise Bailout;
          assert(nofWinsB >= 0);
          if (nofWinsB > 0) {
            CallCopyWithinSortArray(context, sortState, cursorB, dest, nofWinsB)
                otherwise Bailout;

            dest = dest + nofWinsB;
            cursorB = cursorB + nofWinsB;
            lengthB = lengthB - nofWinsB;

            if (lengthB == 0) goto Succeed;
          }
          CallStore(context, sortState, store, dest++, tempArray[cursorTemp++])
              otherwise Bailout;
          if (--lengthA == 1) goto CopyB;
        }
        ++minGallop;  // Penalize it for leaving galloping mode
        sortState[kMinGallopIdx] = minGallop;
      }
    }
    label Succeed {
      if (lengthA > 0) {
        CallCopyFromTempArray(context, sortState, dest, cursorTemp, lengthA)
            otherwise Bailout;
      }
    }
    label CopyB {
      assert(lengthA == 1 && lengthB > 0);
      // The last element of run A belongs at the end of the merge.
      CallCopyWithinSortArray(context, sortState, cursorB, dest, lengthB)
          otherwise Bailout;
      CallStore(
          context, sortState, store, dest + lengthB, tempArray[cursorTemp])
          otherwise Bailout;
    }
  }

  // Merge the lengthA elements starting at baseA with the lengthB elements
  // starting at baseB in a stable way, in-place. lengthA and lengthB must
  // be > 0. Must also have that array[baseA + lengthA - 1] belongs at the
  // end of the merge and should have lengthA >= lengthB.
  transitioning macro MergeHigh(
      context: Context, sortState: FixedArray, baseA: Smi, lengthAArg: Smi,
      baseB: Smi, lengthBArg: Smi)
      labels Bailout {
    assert(0 < lengthAArg && 0 < lengthBArg);
    assert(0 <= baseA && 0 < baseB);
    assert(baseA + lengthAArg == baseB);

    let lengthA: Smi = lengthAArg;
    let lengthB: Smi = lengthBArg;

    const load: LoadFn = GetLoadFn(sortState);
    const store: StoreFn = GetStoreFn(sortState);

    const tempArray: FixedArray = GetTempArray(sortState, lengthB);
    CopyToTempArray(context, sortState, load, baseB, tempArray, 0, lengthB)
        otherwise Bailout;

    // MergeHigh merges the two runs backwards.
    let dest: Smi = baseB + lengthB - 1;
    let cursorTemp: Smi = lengthB - 1;
    let cursorA: Smi = baseA + lengthA - 1;

    CopyElement(context, sortState, load, store, cursorA--, dest--)
        otherwise Bailout;

    try {
      if (--lengthA == 0) goto Succeed;
      if (lengthB == 1) goto CopyA;

      let minGallop: Smi = UnsafeCast<Smi>(sortState[kMinGallopIdx]);
      // TODO(szuend): Replace with something that does not have a runtime
      //               overhead as soon as its available in Torque.
      while (Int32TrueConstant()) {
        let nofWinsA: Smi = 0;  // # of times A won in a row.
        let nofWinsB: Smi = 0;  // # of times B won in a row.

        // Do the straightforward thing until (if ever) one run appears to
        // win consistently.
        // TODO(szuend): Replace with something that does not have a runtime
        //               overhead as soon as its available in Torque.
        while (Int32TrueConstant()) {
          assert(lengthA > 0 && lengthB > 1);

          let elementA: Object = CallLoad(context, sortState, load, cursorA)
              otherwise Bailout;
          let order: Number =
              CallCompareFn(context, sortState, tempArray[cursorTemp], elementA)
              otherwise Bailout;

          if (order < 0) {
            CopyElement(context, sortState, load, store, cursorA, dest)
                otherwise Bailout;

            --cursorA;
            --dest;
            ++nofWinsA;
            --lengthA;
            nofWinsB = 0;

            if (lengthA == 0) goto Succeed;
            if (nofWinsA >= minGallop) break;
          } else {
            CallStore(context, sortState, store, dest, tempArray[cursorTemp])
                otherwise Bailout;

            --cursorTemp;
            --dest;
            ++nofWinsB;
            --lengthB;
            nofWinsA = 0;

            if (lengthB == 1) goto CopyA;
            if (nofWinsB >= minGallop) break;
          }
        }

        // One run is winning so consistently that galloping may be a huge win.
        // So try that, and continue galloping until (if ever) neither run
        // appears to be winning consistently anymore.
        ++minGallop;
        let firstIteration: bool = true;
        while (nofWinsA >= kMinGallopWins || nofWinsB >= kMinGallopWins ||
               firstIteration) {
          firstIteration = false;

          assert(lengthA > 0 && lengthB > 1);

          minGallop = SmiMax(1, minGallop - 1);
          sortState[kMinGallopIdx] = minGallop;

          let k: Smi = CallGallopRight(
              context, sortState, load, tempArray[cursorTemp], baseA, lengthA,
              lengthA - 1)
              otherwise Bailout;
          assert(k >= 0);
          nofWinsA = lengthA - k;

          if (nofWinsA > 0) {
            dest = dest - nofWinsA;
            cursorA = cursorA - nofWinsA;
            CallCopyWithinSortArray(
                context, sortState, cursorA + 1, dest + 1, nofWinsA)
                otherwise Bailout;

            lengthA = lengthA - nofWinsA;
            if (lengthA == 0) goto Succeed;
          }
          CallStore(context, sortState, store, dest--, tempArray[cursorTemp--])
              otherwise Bailout;
          if (--lengthB == 1) goto CopyA;

          let key: Object = CallLoad(context, sortState, load, cursorA)
              otherwise Bailout;
          k = CallGallopLeft(
              context, sortState, Load<TempArrayElements>, key, 0, lengthB,
              lengthB - 1) otherwise Bailout;
          assert(k >= 0);
          nofWinsB = lengthB - k;

          if (nofWinsB > 0) {
            dest = dest - nofWinsB;
            cursorTemp = cursorTemp - nofWinsB;
            CallCopyFromTempArray(
                context, sortState, dest + 1, cursorTemp + 1, nofWinsB)
                otherwise Bailout;

            lengthB = lengthB - nofWinsB;
            if (lengthB == 1) goto CopyA;

            // lengthB == 0 is impossible now if the comparison function is
            // consistent, but we can't assume that it is.
            if (lengthB == 0) goto Succeed;
          }
          CopyElement(context, sortState, load, store, cursorA--, dest--)
              otherwise Bailout;
          if (--lengthA == 0) goto Succeed;
        }
        ++minGallop;
        sortState[kMinGallopIdx] = minGallop;
      }
    }
    label Succeed {
      if (lengthB > 0) {
        assert(lengthA == 0);
        CallCopyFromTempArray(
            context, sortState, dest - (lengthB - 1), 0, lengthB)
            otherwise Bailout;
      }
    }
    label CopyA {
      assert(lengthB == 1 && lengthA > 0);

      // The first element of run B belongs at the front of the merge.
      dest = dest - lengthA;
      cursorA = cursorA - lengthA;
      CallCopyWithinSortArray(
          context, sortState, cursorA + 1, dest + 1, lengthA)
          otherwise Bailout;
      CallStore(context, sortState, store, dest, tempArray[cursorTemp])
          otherwise Bailout;
    }
  }

  // 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;
  }

  // Returns true iff run_length(n - 2) > run_length(n - 1) + run_length(n).
  macro RunInvariantEstablished(implicit context: Context)(
      pendingRuns: FixedArray, n: Smi): bool {
    if (n < 2) return true;

    const runLengthN: Smi = GetPendingRunLength(pendingRuns, n);
    const runLengthNM: Smi = GetPendingRunLength(pendingRuns, n - 1);
    const runLengthNMM: Smi = GetPendingRunLength(pendingRuns, n - 2);

    return runLengthNMM > runLengthNM + runLengthN;
  }

  // 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: FixedArray)
      labels Bailout {
    const pendingRuns: FixedArray =
        UnsafeCast<FixedArray>(sortState[kPendingRunsIdx]);

    // 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;
        }

        CallMergeAt(context, sortState, n) otherwise Bailout;
      } else if (
          GetPendingRunLength(pendingRuns, n) <=
          GetPendingRunLength(pendingRuns, n + 1)) {
        CallMergeAt(context, sortState, n) otherwise Bailout;
      } else {
        break;
      }
    }
  }

  // Regardless of invariants, merge all runs on the stack until only one
  // remains. This is used at the end of the mergesort.
  transitioning macro
  MergeForceCollapse(context: Context, sortState: FixedArray)
      labels Bailout {
    let pendingRuns: FixedArray =
        UnsafeCast<FixedArray>(sortState[kPendingRunsIdx]);

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

      if (n > 0 &&
          GetPendingRunLength(pendingRuns, n - 1) <
              GetPendingRunLength(pendingRuns, n + 1)) {
        --n;
      }
      CallMergeAt(context, sortState, n) otherwise Bailout;
    }
  }

  macro InitializeSortState(sortState: FixedArray) {
    sortState[kMinGallopIdx] = SmiConstant(kMinGallopWins);
    sortState[kTempArraySizeIdx] = SmiConstant(0);

    SetPendingRunsSize(sortState, 0);
    let pendingRuns: FixedArray =
        AllocateZeroedFixedArray(Convert<intptr>(kMaxMergePending));
    sortState[kPendingRunsIdx] = pendingRuns;
  }

  macro InitializeSortStateAccessor<Accessor: type>(sortState: FixedArray) {
    sortState[kAccessorIdx] = kFastElementsAccessorId;
    sortState[kLoadFnIdx] = Load<Accessor>;
    sortState[kStoreFnIdx] = Store<Accessor>;
    sortState[kCanUseSameAccessorFnIdx] = CanUseSameAccessor<Accessor>;
  }

  InitializeSortStateAccessor<GenericElementsAccessor>(sortState: FixedArray) {
    sortState[kAccessorIdx] = kGenericElementsAccessorId;
    sortState[kLoadFnIdx] = Load<GenericElementsAccessor>;
    sortState[kStoreFnIdx] = Store<GenericElementsAccessor>;
    sortState[kCanUseSameAccessorFnIdx] =
        CanUseSameAccessor<GenericElementsAccessor>;
  }

  transitioning macro
  ArrayTimSortImpl(context: Context, sortState: FixedArray, length: Smi)
      labels Bailout {
    InitializeSortState(sortState);

    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(context, sortState, low, low + remaining)
          otherwise Bailout;

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

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

      MergeCollapse(context, sortState) otherwise Bailout;

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

    MergeForceCollapse(context, sortState) otherwise Bailout;
    assert(GetPendingRunsSize(sortState) == 1);
    assert(
        GetPendingRunLength(
            UnsafeCast<FixedArray>(sortState[kPendingRunsIdx]), 0) == length);
  }

  transitioning builtin
  ArrayTimSort(context: Context, sortState: FixedArray, length: Smi): Object {
    try {
      ArrayTimSortImpl(context, sortState, length)
          otherwise Slow;
    }
    label Slow {
      if (sortState[kAccessorIdx] == kGenericElementsAccessorId) {
        // We were already on the slow path. This must not happen.
        unreachable;
      }
      sortState[kBailoutStatusIdx] = kSuccess;

      InitializeSortStateAccessor<GenericElementsAccessor>(sortState);
      ArrayTimSort(context, sortState, length);
    }
    return kSuccess;
  }

  // For compatibility with JSC, we also sort elements inherited from
  // the prototype chain on non-Array objects.
  // We do this by copying them to this object and sorting only
  // own elements. This is not very efficient, but sorting with
  // inherited elements happens very, very rarely, if at all.
  // The specification allows "implementation dependent" behavior
  // if an element on the prototype chain has an element that
  // might interact with sorting.
  //
  // We also move all non-undefined elements to the front of the
  // array and move the undefineds after that. Holes are removed.
  // This happens for Array as well as non-Array objects.
  extern runtime PrepareElementsForSort(Context, Object, Number): Smi;

  // https://tc39.github.io/ecma262/#sec-array.prototype.sort
  transitioning javascript builtin
  ArrayPrototypeSort(context: Context, receiver: Object, ...arguments): Object {
    // 1. If comparefn is not undefined and IsCallable(comparefn) is false,
    //    throw a TypeError exception.
    const comparefnObj: Object = arguments[0];
    if (comparefnObj != Undefined && !TaggedIsCallable(comparefnObj)) {
      ThrowTypeError(context, kBadSortComparisonFunction, comparefnObj);
    }

    // 2. Let obj be ? ToObject(this value).
    const obj: JSReceiver = ToObject(context, receiver);

    const sortState: FixedArray = AllocateZeroedFixedArray(kSortStateSize);

    sortState[kReceiverIdx] = obj;
    sortState[kUserCmpFnIdx] = comparefnObj;
    sortState[kSortComparePtrIdx] =
        comparefnObj != Undefined ? SortCompareUserFn : SortCompareDefault;
    sortState[kBailoutStatusIdx] = kSuccess;

    // 3. Let len be ? ToLength(? Get(obj, "length")).
    const len: Number = GetLengthProperty(obj);

    if (len < 2) return receiver;

    // TODO(szuend): Investigate performance tradeoff of skipping this step
    //               for PACKED_* and handling Undefineds during sorting.
    const nofNonUndefined: Smi = PrepareElementsForSort(context, obj, len);
    assert(nofNonUndefined <= len);

    let map: Map = obj.map;
    sortState[kInitialReceiverMapIdx] = map;
    sortState[kInitialReceiverLengthIdx] = len;

    try {
      GotoIfForceSlowPath() otherwise Slow;
      let a: FastJSArray = Cast<FastJSArray>(receiver) otherwise Slow;

      const elementsKind: ElementsKind = map.elements_kind;
      if (IsDoubleElementsKind(elementsKind)) {
        InitializeSortStateAccessor<FastDoubleElements>(sortState);
      } else if (elementsKind == PACKED_SMI_ELEMENTS) {
        InitializeSortStateAccessor<FastPackedSmiElements>(sortState);
      } else {
        InitializeSortStateAccessor<FastSmiOrObjectElements>(sortState);
      }
      ArrayTimSort(context, sortState, nofNonUndefined);
    }
    label Slow {
      if (map.elements_kind == DICTIONARY_ELEMENTS && IsExtensibleMap(map) &&
          !IsCustomElementsReceiverInstanceType(map.instance_type)) {
        InitializeSortStateAccessor<DictionaryElements>(sortState);
      } else {
        InitializeSortStateAccessor<GenericElementsAccessor>(sortState);
      }
      ArrayTimSort(context, sortState, nofNonUndefined);
    }

    return receiver;
  }
}