mergeSort<E> function

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

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, that 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 mergeSort<E>(List<E> elements,
    {int start = 0, int? end, int Function(E, E)? compare}) {
  end = RangeError.checkValidRange(start, end, elements.length);
  compare ??= defaultCompare;

  var length = end - start;
  if (length < 2) return;
  if (length < _mergeSortLimit) {
    insertionSort(elements, 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 allows the sorted elements to end up in the original list.
  var firstLength = (end - start) >> 1;
  var middle = start + firstLength;
  var secondLength = end - middle;
  // secondLength is always the same as firstLength, or one greater.
  var scratchSpace = elements.sublist(0, secondLength);
  _mergeSort(elements, identity<E>, compare, middle, end, scratchSpace, 0);
  var firstTarget = end - firstLength;
  _mergeSort(
      elements, identity<E>, compare, start, middle, elements, firstTarget);
  _merge(identity<E>, compare, elements, firstTarget, end, scratchSpace, 0,
      secondLength, elements, start);
}