# 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 = List<E>.filled(secondLength, elements[start]);
E Function(E) id = identity;
_mergeSort(elements, id, compare, middle, end, scratchSpace, 0);
var firstTarget = end - firstLength;
_mergeSort(elements, id, compare, start, middle, elements, firstTarget);
_merge(id, compare, elements, firstTarget, end, scratchSpace, 0, secondLength,
elements, start);
}``````