stableSort<T> function

void stableSort<T>(
  1. List<T> list,
  2. {int start = 0,
  3. int? end,
  4. int compare(
    1. T a,
    2. T b
    )?}
)

Copied from algorithms.dart, Copyright (c) 2013, the Dart project authors. Sorts a list between start (inclusive) and end (exclusive) using the merge sort algorithm. If compare is omitted, this defaults to calling Comparable.compareTo on the objects. If any object is not Comparable, this throws a TypeError. Merge-sorting works by splitting the job into two parts, sorting each recursively, and then merging the two sorted parts. This takes on the order of n * log(n) comparisons and moves to sort n elements, but requires extra space of about the same size as the list being sorted. This merge sort is stable: Equal elements end up in the same order as they started in.

Implementation

void stableSort<T>(List<T> list, {int start = 0, int? end, int Function(T a, T b)? compare}) {
  end ??= list.length;
  compare ??= defaultCompare<T?>();

  int length = end - start;
  if (length < 2) return;
  if (length < _MERGE_SORT_LIMIT) {
    _insertionSort(list, compare: compare, start: start, end: end);
    return;
  }
  int middle = start + ((end - start) >> 1);
  int firstLength = middle - start;
  int secondLength = end - middle;
  var scratchSpace = List<T>.filled(secondLength, list[start]);
  _mergeSort(list, compare, middle, end, scratchSpace, 0);
  int firstTarget = end - firstLength;
  _mergeSort(list, compare, start, middle, list, firstTarget);
  _merge(compare, list, firstTarget, end, scratchSpace, 0, secondLength, list, start);
}