void mergeSort()

in lib/src/algorithms.dart [208:236]

• 21 lines of code
• 3 McCabe index (conditional complexity)

void mergeSort<E>(List<E> elements,
    {int start = 0, int? end, int Function(E, E)? compare}) {
  end = RangeError.checkValidRange(start, end, elements.length);
  compare ??= defaultCompare;

  var length = end - start;
  if (length < 2) return;
  if (length < _mergeSortLimit) {
    insertionSort(elements, 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 allows the sorted elements to end up in the original list.
  var firstLength = (end - start) >> 1;
  var middle = start + firstLength;
  var secondLength = end - middle;
  // secondLength is always the same as firstLength, or one greater.
  var scratchSpace = List<E>.filled(secondLength, elements[start]);
  E Function(E) id = identity;
  _mergeSort(elements, id, compare, middle, end, scratchSpace, 0);
  var firstTarget = end - firstLength;
  _mergeSort(elements, id, compare, start, middle, elements, firstTarget);
  _merge(id, compare, elements, firstTarget, end, scratchSpace, 0, secondLength,
      elements, start);
}