mergeSort<T> function

void mergeSort <T>(List<T> list, { int start: 0, int end, int compare(T a, T b) })

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 CastError.

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<T>(List<T> list,
    {int start: 0, int end, int compare(T a, T b)}) {
  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;
  }
  // 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.
  int middle = start + ((end - start) >> 1);
  int firstLength = middle - start;
  int secondLength = end - middle;
  // secondLength is always the same as firstLength, or one greater.
  var scratchSpace = new List<T>(secondLength);
  _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);
}