mergeSort<T> function

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

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 (The stack trace may call it _CastError or _TypeError, but to catch it, use 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.

For small lists (less than 32 elements), mergeSort automatically uses an insertion sort instead, as that is more efficient for small lists. The insertion sort is also stable.

Implementation

void mergeSort<T>(
  List<T> list, {
  int start = 0,
  int? end,
  int Function(T, T)? compare,
}) {
  end ??= list.length;
  compare ??= _defaultCompare<T>();

  final int length = end - start;
  if (length < 2) {
    return;
  }
  if (length < _kMergeSortLimit) {
    _insertionSort<T>(list, compare: compare, start: start, end: end);
    return;
  }
  // Special case the first split instead of directly calling _mergeSort,
  // because the _mergeSort requires its target to be different from its source,
  // and it requires extra space of the same size as the list to sort. This
  // split allows us to have only half as much extra space, and it ends up in
  // the original place.
  final int middle = start + ((end - start) >> 1);
  final int firstLength = middle - start;
  final int secondLength = end - middle;
  // secondLength is always the same as firstLength, or one greater.
  final List<T> scratchSpace = List<T>.filled(secondLength, list[start]);
  _mergeSort<T>(list, compare, middle, end, scratchSpace, 0);
  final int firstTarget = end - firstLength;
  _mergeSort<T>(list, compare, start, middle, list, firstTarget);
  _merge<T>(compare, list, firstTarget, end, scratchSpace, 0, secondLength, list, start);
}