mergeSort<T> function
Null safety
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, list[start]);
_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);
}