# mergeSort<T> function Null safety

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 (The stack trace may call it `_CastError` or `_TypeError`, but to catch it, use 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.

For small lists (less than 32 elements), `mergeSort` automatically uses an insertion sort instead, as that is more efficient for small lists. The insertion sort is also stable.

## Implementation

``````void mergeSort<T>(
List<T> list, {
int start = 0,
int? end,
int Function(T, T)? compare,
}) {
end ??= list.length;
compare ??= _defaultCompare<T>();

final int length = end - start;
if (length < 2) {
return;
}
if (length < _kMergeSortLimit) {
_insertionSort<T>(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.
final int middle = start + ((end - start) >> 1);
final int firstLength = middle - start;
final int secondLength = end - middle;
// secondLength is always the same as firstLength, or one greater.
final List<T?> scratchSpace = List<T?>.filled(secondLength, null, growable: false);
_mergeSort<T>(list, compare, middle, end, scratchSpace, 0);
final int firstTarget = end - firstLength;
_mergeSort<T>(list, compare, start, middle, list, firstTarget);
_merge<T>(compare, list, firstTarget, end, scratchSpace, 0, secondLength, list, start);
}``````