insertionSort<E> function
Null safety
Sort a list between start
(inclusive) and end
(exclusive) using
insertion sort.
If compare
is omitted, this defaults to calling Comparable.compareTo on
the objects. In this case, the objects must be Comparable.
Insertion sort is a simple sorting algorithm. For n
elements it does on
the order of n * log(n)
comparisons but up to n
squared moves. The
sorting is performed in-place, without using extra memory.
For short lists the many moves have less impact than the simple algorithm, and it is often the favored sorting algorithm for short lists.
This insertion sort is stable: Equal elements end up in the same order as they started in.
Implementation
void insertionSort<E>(List<E> elements,
{int Function(E, E)? compare, int start = 0, int? end}) {
// If the same method could have both positional and named optional
// parameters, this should be (list, [start, end], {compare}).
compare ??= defaultCompare;
end ??= elements.length;
for (var pos = start + 1; pos < end; pos++) {
var min = start;
var max = pos;
var element = elements[pos];
while (min < max) {
var mid = min + ((max - min) >> 1);
var comparison = compare(element, elements[mid]);
if (comparison < 0) {
max = mid;
} else {
min = mid + 1;
}
}
elements.setRange(min + 1, pos + 1, elements, min);
elements[min] = element;
}
}