insertionSort<T> function

void insertionSort <T>(List<T> list, { int compare(T a, T b), int start: 0, int end })

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. If any object is not Comparable, this throws a CastError.

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<T>(List<T> list,
    {int compare(T a, T b), 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<T>();
  end ??= list.length;

  for (int pos = start + 1; pos < end; pos++) {
    int min = start;
    int max = pos;
    var element = list[pos];
    while (min < max) {
      int mid = min + ((max - min) >> 1);
      int comparison = compare(element, list[mid]);
      if (comparison < 0) {
        max = mid;
      } else {
        min = mid + 1;
      }
    }
    list.setRange(min + 1, pos + 1, list, min);
    list[min] = element;
  }
}