# 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);
}``````