# mergeSort<T> function

void mergeSort <T>(
1. List<T> list,
2. {int start: 0,
3. int end,
4. int compare(
1. T,
2. T
)}
)

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 TypeError (`CastError` on some SDK versions).

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 Function(T, T) compare}) {
end ??= list.length;
compare ??= defaultCompare<T>();

var 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.
var middle = start + ((end - start) >> 1);
var firstLength = middle - start;
var secondLength = end - middle;
// secondLength is always the same as firstLength, or one greater.
var scratchSpace = List<T>(secondLength);
_mergeSort(list, compare, middle, end, scratchSpace, 0);
var firstTarget = end - firstLength;
_mergeSort(list, compare, start, middle, list, firstTarget);
_merge(compare, list, firstTarget, end, scratchSpace, 0, secondLength, list,
start);
}``````