# mergeSort<E> function

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 = List<E>.filled(secondLength, elements[start]);
_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);
}
```