Array.prototype.sort: How V8 Sorts Without Crashing the Stack

TL;DR: third_party/v8/builtins/array-sort.tq implements PowerSort, a stable adaptive merge sort ported from CPython’s listobject.c. The interesting part is not the merge - that is textbook - but the decision of what to merge next. Classic TimSort merges when the left run is longer than the right; PowerSort computes the depth of each boundary in the merge tree (NodePower) and merges when the depths would come out unbalanced. The result is a merge tree that is balanced by construction, so no input can force a quadratic number of comparisons.

Array.prototype.sort is one of those functions where the obvious implementation is a trap. You write a quicksort, and then somebody feeds it an array of a thousand identical elements and your server falls over. You write a heapsort, and then the sort is stable no more.

V8’s answer is to be adaptive: find the runs that are already sorted and merge them in a way that cannot be quadratic. The implementation is a port of CPython’s listobject.c, and the file says so:

cpp
// third_party/v8/builtins/array-sort.tq:5
// This file implements a stable, adaptive merge sort variant called PowerSort.
//
// 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

The shape of the thing

Array.prototype.sort is a Torque builtin, but not a Torque macro - it is a JavaScript builtin with a C++-shaped body that calls into the runtime:

cpp
// third_party/v8/builtins/array-sort.tq:1592
transitioning javascript builtin ArrayPrototypeSort(
    js-implicit context: NativeContext, receiver: JSAny)(...arguments): JSAny {
  // 1. If comparefn is not undefined and IsCallable(comparefn) is false,
  //    throw a TypeError exception.
  const comparefnObj: JSAny = arguments[0];
  const comparefn = Cast<(Undefined | Callable)>(comparefnObj) otherwise
  ThrowTypeError(MessageTemplate::kBadSortComparisonFunction, comparefnObj);

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

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

  if (len < 2) return obj;

  const isToSorted: constexpr bool = false;
  const sortState: SortState = NewSortState(obj, comparefn, len, isToSorted);
  ArrayPowerSort(context, sortState);

  return obj;
}

Everything between NewSortState and ArrayPowerSort is bookkeeping. The state lives in a heap-allocated SortState object, not in C++ locals - Torque’s calling convention does not let you allocate structs:

cpp
// third_party/v8/builtins/array-sort.tq:24
@cppObjectLayoutDefinition
extern class SortState extends HeapObject {
  // The receiver of the Array.p.sort call.
  receiver: JSReceiver;

  // 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.
  initial_receiver_map: Map;
  initial_receiver_length: Number;

  // If the user provided a comparison function, it is stored here.
  user_cmp_fn: Undefined|Callable;

  is_reset_to_generic: Boolean;

  // 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.
  min_gallop: Smi;

The C++ mirror in src/objects/sort-state.h is a plain TaggedMember soup with no accessors: “SortState’s fields are accessed exclusively from Torque-generated code.”

Array.prototype.toSorted shares the entire implementation; the only difference is the isToSorted constexpr flag, which switches between “sort in place” and “sort a copy”.

The work array: a snapshot, and why it exists

Before anything is sorted, the receiver’s elements are copied into a work_array that user code cannot touch. This is not an optimisation; it is a correctness requirement.

The spec (ECMA-262, Array.prototype.sort) defines the algorithm in terms of an items list that is a snapshot of the array’s elements taken before any comparison happens. A comparison function is arbitrary JavaScript, and it can mutate the array being sorted; if the sort read elements lazily from the receiver, the result would depend on the comparator’s side effects.

V8’s snapshot is CompactReceiverElementsIntoWorkArray, and the fast path is a straight copy of the elements store:

cpp
// third_party/v8/builtins/array-sort.tq:1404
  if ((sortState.is_reset_to_generic == False) &&
      Is<FastJSArray>(sortState.receiver)) {
    const fastArray = UnsafeCast<FastJSArray>(sortState.receiver);
    const elementsKind: ElementsKind = fastArray.map.elements_kind;
    if (!IsDoubleElementsKind(elementsKind)) {
      // Fast path for Smi and Object elements
      const elements = UnsafeCast<FixedArray>(fastArray.elements);
      for (let i: Smi = 0; i < receiverLength; ++i) {
        const element: Object = elements.objects[i];

        if (element == TheHole) {
          if constexpr (isToSorted) {
            // Array.prototype.toSorted does not have the HasProperty check
            // that Array.prototype.sort has and unconditionally performs a
            // GetProperty for each element.
            //
            // Only fast JSArray accessors return TheHole, and fast JSArrays
            // are protected by the NoElements protector which ensures that
            // objects on the prototype chain do not have indexed properties.
            // So if a fast JSArray accessor returns TheHole, we know the
            // prototype walk will return Undefined.
            numberOfUndefined++;
          } else {
            // Do nothing for holes for Array.prototype.sort. The result
            // is that elements are compacted at the front of the work array.
          }
        } else if (element == Undefined) {
          numberOfUndefined++;
        } else {
          growableWorkArray.Push(UnsafeCast<JSAny>(element));
        }
      }
    } else {

Three behaviours fall out of this loop, and they are all spec requirements that are easy to get wrong: holes are removed (and deleted after the sort), undefined is moved to the end without calling the comparator, and a comparator that throws on undefined will not throw.

The work array is a GrowableFixedArray, so it can grow beyond the initial allocation. Its initial size is guessed by CalculateWorkArrayLength: the length property is an upper bound (per the spec) and the actual backing store size is a better guess, so the minimum of the two is used, clamped to kSmiMaxValue. That clamp is the source’s TODO - sorting an array with more than 2^31 elements is not supported.

That is the whole snapshotting story for the generic path. The compiler’s inlined path takes its own snapshot; we come back to it.

Calling the comparator

The comparator call is the hot path, and there are two versions: with and without a user function.

cpp
// third_party/v8/builtins/array-sort.tq:80
transitioning macro Compare(
    implicit context: Context)(sortState: SortState, x: JSAny,
    y: JSAny): Number {
  if (sortState.user_cmp_fn != Undefined) {
    return SortCompareUserFn(context, sortState.user_cmp_fn, x, y);
  } else {
    return SortCompareDefault(context, sortState.user_cmp_fn, x, y);
  }
}

and the user-function version:

cpp
// third_party/v8/builtins/array-sort.tq:402
transitioning builtin SortCompareUserFn(
    context: Context, comparefn: JSAny, x: JSAny, y: JSAny): Number {
  dcheck(comparefn != Undefined);
  const cmpfn = UnsafeCast<Callable>(comparefn);

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

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

  // c. return v.
  return v;
}

Two details matter here. The comparator is called with undefined as this - the spec says so, and it means a comparator that uses this gets undefined rather than the array. And NaN is normalised to +0, the spec’s “if the result is NaN, treat it as +0” rule, which is what makes the sort stable: a comparator that returns NaN for a pair treats them as equal, and equal elements must keep their relative order.

Note what V8 does not do: it does not memoise comparison results. Every comparison is a fresh call into the user’s function, and the sort’s only defence against an expensive comparator is to make fewer comparisons - which is what the adaptive run detection, the galloping, and the compiler’s inlining of the small-array case are for. (The elements are cached, in the work array; the comparison results are not.)

The default comparator is a string comparison:

cpp
// third_party/v8/builtins/array-sort.tq:378
transitioning builtin SortCompareDefault(
    context: Context, comparefn: JSAny, x: JSAny, y: JSAny): Number {
  dcheck(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(x);

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

  // 7. Let xSmaller be the result of performing
  //    Abstract Relational Comparison xString < yString.
  // 8. If xSmaller is true, return -1.
  // 9. Let ySmaller be the result of performing
  //    Abstract Relational Comparison yString < xString.
  // 10. If ySmaller is true, return 1.
  // 11. Return +0.
  return StringCompare(xString, yString);
}

The SmiLexicographicCompare fast path skips the string conversion when both elements are small integers, but the result is still lexicographic: [10, 9].sort() gives [10, 9].

The merge tree: the actually clever part

Here is where PowerSort differs from the TimSort it descends from.

A classic TimSort maintains a stack of pending runs and merges when the top two runs violate the “left longer than right” invariant. That guarantees O(n log n) comparisons, but the shape of the merge tree is not balanced - it depends on the run structure of the input, and an adversarial input can produce a tree of depth O(n).

PowerSort replaces the “run length” invariant with a “tree depth” invariant. Each pending run has a power: the depth it would occupy in an optimal binary merge tree. The merge happens when merging would produce a deeper-than-necessary tree.

Computing the exact depth of a boundary requires two divisions by the total length n, and doing that in floating point loses precision for large n. So V8 computes it in fixed point, with a 32-bit fallback:

cpp
// third_party/v8/builtins/array-sort.tq:502
// Computes the depth of a boundary in a merge tree.
// Uses a 64-bit fast path on 64-bit platforms, or falls back to NodePower32.
@export
macro NodePower(
    implicit context: Context)(s1: Smi, n1: Smi, n2: Smi, n: Smi): Smi {
  dcheck(s1 >= 0);
  dcheck(n1 > 0 && n2 > 0);
  dcheck(s1 + n1 + n2 <= n);

  if constexpr (!Is64()) {
    return NodePower32(s1, n1, n2, n);
  } else {
    const a: intptr = 2 * Convert<intptr>(s1) + Convert<intptr>(n1);
    const b: intptr = a + Convert<intptr>(n1) + Convert<intptr>(n2);
    const nPtr: intptr = Convert<intptr>(n);

    // Compute (a << 30) / n and (b << 30) / n
    const aScaled: intptr = (a << 30) / nPtr;
    const bScaled: intptr = (b << 30) / nPtr;

    const a32: uint32 = Unsigned(Convert<int32>(aScaled));
    const b32: uint32 = Unsigned(Convert<int32>(bScaled));

    const a64: uint64 = Convert<uint64>(a32);
    const b64: uint64 = Convert<uint64>(b32);
    const diff64 = Word64Xor(a64, b64);
    const diff32 = Convert<uint32>(diff64);
    const result: int32 = math::Word32Clz(Signed(diff32));

    return Convert<Smi>(result);
  }
}

Read that carefully. It scales a and b by 2^30 before dividing, so the quotient has 30 bits of fractional precision. Then it XORs the two 32-bit results and counts the leading zeros - and the number of leading zeros is the position of the most significant bit where the two scaled quotients differ, which is the depth of the boundary.

The trick is that you do not need the exact quotients, only the position of the highest bit where they differ. Word32Clz is a single instruction on x86 and ARM.

The 32-bit fallback does the same thing a bit at a time:

cpp
// third_party/v8/builtins/array-sort.tq:477
macro NodePower32(
    implicit context: Context)(s1: Smi, n1: Smi, n2: Smi, n: Smi): Smi {
  let result: Smi = 0;
  let a: intptr = 2 * Convert<intptr>(s1) + Convert<intptr>(n1);  // 2*a
  let b: intptr = a + Convert<intptr>(n1) + Convert<intptr>(n2);  // 2*b
  const nPtr: intptr = Convert<intptr>(n);

  // Emulate a/n and b/n one bit at a time, until bits differ.
  while (true) {
    result = result + 1;
    if (a >= nPtr) {
      // Both quotient bits are 1
      a = a - nPtr;
      b = b - nPtr;
    } else if (b >= nPtr) {
      // Quotient bits differ (a/n bit is 0, b/n bit is 1)
      break;
    }

    a = a << 1;
    b = b << 1;
  }
  return result;
}

The 32-bit version is a long-division loop that computes the two quotients one bit at a time until the bits differ - O(log n), with a loop body of about six instructions.

The run stack

The pending runs live in two FixedArrays on the SortState, the first holding base/length pairs:

cpp
// third_party/v8/builtins/array-sort.tq:45
  // A stack of sortState.pending_runs_size pending runs yet to be merged.
  // Run #i starts at sortState.pending_runs[2 * i] and extends for
  // sortState.pending_runs[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
  //
  pending_runs_size: Smi;
  pending_runs: FixedArray;
  pending_powers: FixedArray;

The second, pending_powers, holds the tree power of each boundary. The stack is bounded:

cpp
// third_party/v8/builtins/array-sort.tq:230
// 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;

85 entries, because the merge tree of a balanced sort of n elements has depth log2(n), and the pending-run stack never needs more than the tree depth. 32 * phi^85 is astronomically larger than 2^64, so the bound is never reached in practice.

The main loop is where the tree balancing happens:

cpp
// third_party/v8/builtins/array-sort.tq:1335
    let stackSize: Smi = GetPendingRunsSize(sortState);

    if (stackSize == 0) {
      PushRun(sortState, low, currentRunLength);
    } else {
      const pendingRuns = sortState.pending_runs;
      const pendingPowers = sortState.pending_powers;

      const prevRunBase = GetPendingRunBase(pendingRuns, stackSize - 1);
      const prevRunLen = GetPendingRunLength(pendingRuns, stackSize - 1);

      const p = NodePower(prevRunBase, prevRunLen, currentRunLength, length);

      while (stackSize > 1 &&
             GetPendingPower(pendingPowers, stackSize - 2) > p) {
        MergeAt(stackSize - 2);
        stackSize = GetPendingRunsSize(sortState);
      }

Read the condition: GetPendingPower(pendingPowers, stackSize - 2) > p. The power of the previous boundary is compared with the power of the new one, and they merge while the previous is deeper. That is the balancing rule: if the older boundary is deeper, leaving them unmerged would create a lopsided tree.

The pending_powers array has a subtlety the comment explains:

cpp
// third_party/v8/builtins/array-sort.tq:1285
// pendingPowers[i] represents the power of the boundary between run i and i+1.
// MergeAt(stackSize - 2) is the correct merge target because we merge when the
// power of the current boundary is strictly less than the power of the previous
// boundary. The merged run's power slot is intentionally left stale because the
// next iteration reads the left neighbor's power, which is unchanged.

“The merged run’s power slot is intentionally left stale” - the kind of comment that only exists because someone got it wrong once.

And here is the answer to the question in the title: the pending-run stack is a FixedArray on the V8 heap, not a C++ stack. The whole sort is iterative - ArrayPowerSortImpl loops over the array, finds runs, pushes them, and merges them when the tree says so. There is no recursion anywhere in Array.prototype.sort, so sorting a ten-million-element array does not need ten million stack frames. (Contrast with TypedArray.prototype.sort with a custom comparator, which is a recursive merge sort - see below. Its recursion depth is log2(n), so it is fine, but it is a different shape.)

Natural runs and the minimum run length

Before the merge machinery, the array is chopped into natural runs. A run is a maximal ascending (or strictly descending, then reversed) sequence:

cpp
// third_party/v8/builtins/array-sort.tq:663
// 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.

The strictness of the descending definition is a stability requirement: if the run were >= instead of >, reversing it would swap two equal elements, and a stable sort must not do that.

Runs shorter than a computed minimum run length are extended using binary insertion sort, and the minimum run length comes from CPython:

cpp
// third_party/v8/builtins/array-sort.tq:1300
  // Port of CPython's minrun_next(): produces balanced run lengths that sum
  // exactly to length, each equal to floor(length/2^e) or ceil(length/2^e).
  // Find e such that floor(length/2^e) is in [32, 64).
  let mrStep: Smi = length;
  let mrMask: Smi = 0;
  while (mrStep >= 64) {
    mrStep = mrStep >> 1;
    mrMask = (mrMask << 1) | 1;
  }
  // mrStep = floor(length/2^e), mrMask = 2^e - 1.
  // Each call: if accumulated remainder overflows 2^e, return mrStep+1,
  // else mrStep. This is equivalent to CPython's mr_current arithmetic.
  const mrRemainder: Smi = length & mrMask;
  const mrThreshold: Smi = mrMask + 1;
  let mrAccum: Smi = 0;

The mrAccum accumulator is the trick: it distributes the remainder across runs so the run lengths sum to exactly length, each being floor(length/2^e) or ceil(length/2^e). The runs are therefore all roughly the same size, so the tree comes out balanced without needing a particular merge order.

Short runs are then sorted with binary insertion sort:

cpp
// third_party/v8/builtins/array-sort.tq:1327
    let currentRunLength: Smi = CountAndMakeRun(low, low + remaining);

    if (currentRunLength < minRunLength) {
      const forcedRunLength: Smi = SmiMin(minRunLength, remaining);
      BinaryInsertionSort(low, low + currentRunLength, low + forcedRunLength);
      currentRunLength = forcedRunLength;
    }

Binary insertion sort is the right choice because the runs are short. The comment explains why:

cpp
// third_party/v8/builtins/array-sort.tq:604
// 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.

“comparisons are more expensive due to calling into JS” - that is the whole justification. A comparison into a user comparator is a full JS call, so minimising comparisons matters more than minimising data movement, and binary insertion sort does O(n log n) comparisons and O(n^2) moves, the right trade for a run of 32 to 64 elements.

Binary insertion sort is also stable, and the code shows how:

cpp
// third_party/v8/builtins/array-sort.tq:635
    // Find pivot insertion point.
    while (left < right) {
      const mid: Smi = left + ((right - left) >> 1);
      const order =
          Compare(sortState, pivot, UnsafeCast<JSAny>(workArray.objects[mid]));

      if (order < 0) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    dcheck(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.

left = mid + 1 on an equal comparison is the entire stability mechanism for insertion sort: the pivot goes after the equal elements, never before them.

Galloping

When one run wins consistently, the merge switches to galloping mode: instead of comparing one element at a time, it does an exponential search to find the whole block of elements that beat the other run’s current element. The threshold is adaptive:

cpp
// third_party/v8/builtins/array-sort.tq:237
// 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;

Seven consecutive wins. The min_gallop field on the SortState is the current threshold, and it moves:

cpp
// third_party/v8/builtins/array-sort.tq:1073
      // 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;
        dcheck(lengthA > 1 && lengthB > 0);

        minGallop = SmiMax(1, minGallop - 1);
        sortState.min_gallop = minGallop;

The threshold starts at 7, is raised by one when entering galloping mode, and lowered by one each time a gallop succeeds, so the sort becomes more eager to gallop on random data and less eager on structured data.

The gallop is an exponential search followed by a binary search:

cpp
// third_party/v8/builtins/array-sort.tq:821
  let lastOfs: Smi = 0;
  let offset: Smi = 1;

  const baseHintElement = UnsafeCast<JSAny>(array.objects[base + hint]);
  let order = Compare(sortState, baseHintElement, key);

  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.
    const maxOfs: Smi = length - hint;
    while (offset < maxOfs) {
      const offsetElement =
          UnsafeCast<JSAny>(array.objects[base + hint + offset]);
      order = Compare(sortState, offsetElement, key);

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

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

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

offset = (offset << 1) + 1 is the exponential probe: 1, 3, 7, 15, 31. And the overflow check is written the clever way: offset is a Smi, so it cannot go negative, but it can wrap to negative on overflow, and offset <= 0 catches that.

After the exponential phase finds a bracket, a binary search narrows it down. There are two variants, differing in where equal elements land:

cpp
// third_party/v8/builtins/array-sort.tq:797
// 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 distinction is a stability requirement: “left of the leftmost equal” and “right of the rightmost equal” are different positions, and using the wrong one would swap equal elements.

Merging

The merge is the standard one, with one twist: it merges in place using a temporary array of size min(lengthA, lengthB).

cpp
// third_party/v8/builtins/array-sort.tq:787
  // 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);
  }

MergeLow copies the smaller run into the temp array and then merges backwards-from-the-front, so the temp array never holds more than half the data. MergeHigh does the mirror image, merging from the back. The temp array is replaced rather than grown in place, because a FixedArray cannot be resized once allocated - so it reallocates the whole thing every time it needs to grow.

The merge loop keeps two win counters and switches to galloping when either reaches the threshold:

cpp
// third_party/v8/builtins/array-sort.tq:1037
    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()) {
        dcheck(lengthA > 1 && lengthB > 0);

        const order = Compare(
            sortState, UnsafeCast<JSAny>(workArray.objects[cursorB]),
            UnsafeCast<JSAny>(tempArray.objects[cursorTemp]));

        if (order < 0) {
          workArray.objects[dest++] = workArray.objects[cursorB++];

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

          if (lengthB == 0) goto Succeed;
          if (nofWinsB >= minGallop) break;
        } else {

Int32TrueConstant() is a Torque idiom for while (true) that the compiler can see through; the “TODO” refers to Torque not having a for(;;) with a known trip count.

The comparator that mutates the array

Back to the hazard: what happens if the comparator mutates the receiver during the sort?

The work array is a snapshot, so the sort result is unaffected - the sorted elements are the ones captured before the first comparison. But the writeback happens at the end, and by then the receiver may have changed shape, so V8 re-checks its map and length before writing back:

cpp
// third_party/v8/builtins/array-sort.tq:1559
transitioning macro ArrayPowerSortTail(
    implicit context: Context, sortState: SortState)(
    numberOfNonUndefined: Smi): void {
  const isToSorted: constexpr bool = false;

  if (numberOfNonUndefined < kMaxBinaryInsertionSortLength) {
    // Faster for small arrays.
    BinaryInsertionSort(0, 0, numberOfNonUndefined);
  } else {
    ArrayPowerSortImpl(context, sortState, numberOfNonUndefined);
  }

  try {
    // The comparison function or toString might have changed the
    // receiver, if that is the case, we switch to the slow path.
    CheckAccessor(sortState) otherwise Slow;
  } label Slow deferred {
    ResetToGenericAccessor(sortState, isToSorted);
  }

  CopyWorkArrayToReceiver(numberOfNonUndefined);
}

CheckAccessor compares the receiver’s current map and length with those recorded at the start:

cpp
// third_party/v8/builtins/array-sort.tq:417
builtin CanUseSameAccessor<ElementsAccessor : type extends ElementsKind>(
    context: Context, receiver: JSReceiver, initialReceiverMap: Map,
    initialReceiverLength: Number): Boolean {
  if (receiver.map != initialReceiverMap) return False;

  dcheck(TaggedIsSmi(initialReceiverLength));
  const array = UnsafeCast<JSArray>(receiver);
  const originalLength = UnsafeCast<Smi>(initialReceiverLength);

  return SelectBooleanConstant(UnsafeCast<Smi>(array.length) == originalLength);
}

If the map changed - the comparator added a property, say - V8 falls back to the generic GetProperty/SetProperty path, which handles whatever shape the array is now in. is_reset_to_generic latches the rest of the code onto the slow path.

And the writeback itself is a three-step process:

cpp
// third_party/v8/builtins/array-sort.tq:1513
  // Writing the elements back is a 3 step process:
  //   1. Copy the sorted elements from the workarray to the receiver.
  //   2. Add {nOfUndefined} undefineds to the receiver.
  //   3. Depending on the backing store either delete properties or
  //      set them to the TheHole up to {sortState.sort_length}.

Step 3 is where the holes go: the spec says holes sort to the end and are then deleted, and for a fast-elements array “deleting” means writing the hole sentinel.

The inlined sort: TurboFan and Maglev

For small arrays, V8 does not call the builtin at all - it inlines an insertion sort into the optimising compiler’s graph, with the comparator call inlined too:

cpp
// src/compiler/js-call-reducer.cc:1763
TNode<Object> IteratingArrayBuiltinReducerAssembler::ReduceArrayPrototypeSort(
    MapInference* inference, const bool has_stability_dependency,
    ElementsKind kind, SharedFunctionInfoRef shared) {
  // Inline a small insertion sort directly into the Turbofan graph.
  //
  // Fast path (length <= kMaxInlineSortLength):
  //   1. Copy receiver's elements into a temporary FixedArray (the spec's
  //      _items_ snapshot per ECMA-262 23.1.3.30).
  //   2. Insertion-sort the temp array, calling comparefn for each
  //      comparison.  After each shift, restore the pivot to temp_array[j]
  //      so that the array remains a valid permutation of the original
  //      elements at every cmp call boundary.
  //   3. Copy sorted elements back into the receiver.

The threshold is 16, and the comment on the constant explains the relationship with the generic path: it uses the same binary insertion sort below the threshold, so the two paths agree on the result:

cpp
// src/objects/js-array.h:137
  // Maximum array length for which Maglev/TurboFan inline an insertion sort
  // instead of calling the generic PowerSort builtin.  PowerSort itself uses
  // BinaryInsertionSort below this threshold too.
  static constexpr int kMaxInlineSortLength = 16;

The hard part of inlining a sort is the deoptimisation. The comparison call can throw, the comparator can change the receiver’s map, the array can grow. V8’s solution is to keep the snapshot alive across the deoptimisation and hand it to the generic sort:

cpp
// src/builtins/array.tq:95
// Deopt continuations for the inlined Array.prototype.sort.  The inlined sort
// took a snapshot of the receiver's elements into temp_array before calling
// comparefn for the first time.  On deopt we hand that snapshot to the generic
// PowerSort tail so that comparefn side effects on the receiver do not affect
// the sort result and the final array remains a permutation of the original
// elements, matching ECMA-262 23.1.3.30 SortIndexedProperties semantics.
//
// The inlined reduction is responsible for keeping temp_array a valid
// permutation of the original elements at every deopt point (the pivot is
// written back into temp_array after each shift in the insertion sort inner
// loop, so the pivot is never stranded in a register only).

“the pivot is written back into temp_array after each shift” is the invariant that makes the deopt resumable: every deopt point has to see a temp_array that is a valid permutation.

The continuation builtins exist on both sides:

cpp
// src/builtins/array.tq:124
transitioning javascript builtin
ArraySortContinueFromSnapshotEagerDeoptContinuation(
    js-implicit context: NativeContext, receiver: JSAny)(comparefn: JSAny,
    tempArray: JSAny, originalLength: JSAny): JSAny {
  const temp = Cast<FixedArray>(tempArray) otherwise unreachable;
  const len = Cast<Smi>(originalLength) otherwise unreachable;
  return ArraySortContinueFromSnapshot(receiver, comparefn, temp, len);
}

Maglev does the same thing, and its comment states the reason for inlining: “avoiding the builtin -> JS transition overhead on every comparefn call inside TimSort”. The comparison is a call from a Torque builtin into JavaScript, which means a stack frame transition, an argument adaptor, a call IC. If the comparator is a known constant function with bytecode, the compiler can inline the whole comparison and the call becomes a jump. (Maglev’s comment still says “TimSort”, a leftover from before the PowerSort port.) Its preconditions are instructive:

cpp
// src/maglev/maglev-graph-builder.cc:9758
  //  2. receiver has known PACKED_SMI or PACKED maps (holey arrays excluded
  //     because holes require special treatment the insertion sort does not
  //     implement; PACKED_DOUBLE excluded so deopt continuations stay simple
  //     -- see below)
  //  3. a comparefn is provided (args[0])
  //  4. comparefn is a statically-known interpreted JSFunction
  //     (HasBytecodeArray);

Four conditions, all about being able to bail out safely. No comparefn means the default comparator path, which is not inlined, and holey arrays would need hole handling the insertion sort lacks.

The PACKED_DOUBLE exclusion has a specific reason:

cpp
// src/maglev/maglev-graph-builder.cc:9776
  // PACKED_DOUBLE is not handled: the generic PowerSort work_array is a
  // FixedArray of boxed HeapNumbers, so bridging the FixedDoubleArray temp
  // into that format on the deopt path requires either pre-boxing in the
  // inlined sort or a separate unboxing continuation builtin.  TF doesn't
  // handle PACKED_DOUBLE either.

Because the deopt path has to hand the snapshot to the generic PowerSort, whose work array is a FixedArray of boxed HeapNumbers, while the inlined sort works on a FixedDoubleArray of unboxed doubles. Bridging the two is the whole problem.

Typed arrays: a different algorithm entirely

TypedArray.prototype.sort is a different implementation entirely. With no comparator it goes to C++ and uses std::sort:

cpp
// src/builtins/typed-array-sort.tq:81
transitioning macro TypedArraySortCommon(
    implicit context: Context)(array: JSTypedArray, len: uintptr,
    comparefnArg: Undefined|Callable, isSort: constexpr bool): JSTypedArray {
  // Arrays of length 1 or less are considered sorted.
  if (len < 2) return array;

  // Default sorting is done in C++ using std::sort
  if (comparefnArg == Undefined) {
    return TypedArraySortFast(context, array);
  }

and std::sort is not a stable sort:

cpp
// src/runtime/runtime-typedarray.cc:110
RUNTIME_FUNCTION(Runtime_TypedArraySortFast) {

That is harmless on the default path, because the comparator is a total order: the only pairs that compare equal are identical values, so there is nothing for stability to preserve. The custom-comparator path is stable - the merge below takes from the left run when the comparison is <= 0.

The C++ comparator shows the special cases:

cpp
// src/runtime/runtime-typedarray.cc:85
template <typename T>
bool CompareNum(T x, T y) {
  if (x < y) {
    return true;
  } else if (x > y) {
    return false;
  } else if (!std::is_integral_v<T>) {
    double _x = x, _y = y;
    if (x == 0 && x == y) {
      /* -0.0 is less than +0.0 */
      return std::signbit(_x) && !std::signbit(_y);
    } else if (!std::isnan(_x) && std::isnan(_y)) {
      /* number is less than NaN */
      return true;
    }
  }
  return false;
}

The std::is_integral_v<T> guard keeps the integer path free of the signbit and isnan checks.Two special cases fall out of that comparator, and the inline comments say what they are: -0.0 sorts before +0.0, and a NaN sorts after every number (“number is less than NaN”). The latter differs from Array.prototype.sort’s default comparator - but that one is a string comparison, so it never has a NaN to place at all.

With a comparator, the typed array sort uses a recursive merge sort in Torque:

cpp
// src/builtins/typed-array-sort.tq:59
transitioning builtin TypedArrayMergeSort(
    implicit context: Context)(source: FixedArray, from: uintptr, to: uintptr,
    target: FixedArray, array: JSTypedArray, comparefn: Callable): JSAny {
  dcheck(to - from > 1);
  const middle: uintptr = from + ((to - from) >>> 1);

  // On the next recursion step source becomes target and vice versa.
  // This saves the copy of the relevant range from the original
  // array into a work array on each recursion step.
  if (middle - from > 1) {
    TypedArrayMergeSort(target, from, middle, source, array, comparefn);
  }
  if (to - middle > 1) {
    TypedArrayMergeSort(target, middle, to, source, array, comparefn);
  }

  TypedArrayMerge(source, from, middle, to, target, array, comparefn);

  return Undefined;
}

Ping-ponging between two work arrays avoids the copy at each level, and the recursion depth is log2(n).

Trade-offs

What it buys.

Stability, guaranteed. Equal elements keep their relative order. The specification has required this of Array.prototype.sort since ES2019, and it is what makes sorting objects by one key while preserving another order work.
No quadratic blowup on any input. The merge tree is balanced by construction via NodePower, so the worst case is O(n log n) comparisons whatever the data looks like.
Few comparisons on structured data. Natural runs are detected and merged without re-comparing, so a sorted array costs O(n).
The comparator’s side effects cannot change the result. The work array snapshot is taken before the first comparison.

What it costs.

O(n) extra memory. The work array is a full copy of the elements. For a 10-million-element array of pointers, that is 80 MB on a 64-bit build.
The comparator is a full JS call. Every comparison goes through Call, which means a stack frame transition and an IC lookup. This is why the compiler inlines the small-array case, and why binary insertion sort (few comparisons, more movement) is preferred for short runs.
Torque is not C++. The sort lives in a language without structs, without templates, and without floating point. The NodePower fixed-point computation is the price of that.
The temp array is reallocated on growth. GetTempArray cannot grow a FixedArray in place, so it allocates a new one and throws the old one away.

The bottom line

The mental model: an adaptive merge sort whose merge tree is balanced by node depth, not run length.

The runs come from CountAndMakeRun (natural ascending or strictly descending sequences), short runs are topped up with binary insertion sort to a minimum length of 32 to 64, and the runs are then merged in an order chosen so the merge tree comes out balanced. That last part is the innovation: NodePower computes the depth a boundary would occupy in an optimal merge tree, and the merge decision compares powers instead of lengths.

Everything else - the galloping, the two merge directions, the in-place merge with a min(lenA, lenB) temp array - is standard adaptive-merge-sort machinery, ported from CPython with the same structure and the same comments.

The thing people get wrong

The belief is that Array.prototype.sort sorts the array in place, element by element, and therefore that a comparator which mutates the array changes the result.

It does not. The sort operates on a snapshot: V8 copies the receiver’s elements into a work_array before it makes the first comparison, sorts the copy, and only writes back at the end. A comparator that clears the array, or appends to it, or reorders it, sees the original contents and its changes are overwritten by the writeback. The spec calls this the items list, and has required it since the sort was specified.

The second misconception is that V8’s sort is “V8’s sort”. It is CPython’s sort. The file header is a Python Software Foundation copyright, and the algorithm - the minrun computation, the pending-run stack, the galloping thresholds - is a direct port of Objects/listobject.c. If you want to understand why the merge tree is balanced by depth, read listsort.txt; it explains it better than anything in the V8 tree.