mergeSort<E> function

void mergeSort<E>(
  1. List<E> list, {
  2. int? begin,
  3. int? end,
  4. Comparator<E>? compare,
  5. int threshold = 8,
})

Sorts the list of numbers using the merge sort algorithm with a few optimizations.

Parameters

  • list is any list of items to be sorted.
  • To perform partial sorting, you can specify the begin or end.
  • begin is the start index of the range to be sorted.
  • If begin is negative, range starts at the 0
  • If begin is not below the length of the list, range will be empty.
  • end is the final index if the range to be sorted. It is exclusive.
  • If end is above the length of the list, it will be ignored.
  • If end is negative, the absolute value of it will be subtracted from the length of the list to determine where the range ends.
  • If end is not greater than the begin, the range will be empty.
  • compare is a custom compare to order the list elements. If it is null and list items are not Comparable, TypeError is thrown.
  • threshold is the maximum limit for which a range can be sorted using insertion sort. It must be a power of 2, otherwise ArgumentError is thrown.

Optimizations

  1. Using iterative approach to avoid recursion. (function calls are slow)
  2. Use insertion sort on smaller ranges. (configurable by threshold parameter)
  3. Reuse working copy of list by swapping after merge (reduces copy operations)
  4. Keeping separate logic for when compare function is provided or not.

Details

Mergesort is a divide and conquer based algorithm, which can handle very large arrays. Unlike quick sort, it promises O(n log n) performance in worst case and provides stable sort. But it performs poorly in practice due to extra memory allocation, and frequent copy operations.

Complexity: Time O(n log n) | Space O(n)

Implementation

void mergeSort<E>(
  List<E> list, {
  int? begin,
  int? end,
  Comparator<E>? compare,
  int threshold = 8,
}) {
  int b, e;
  int n = list.length;

  // Find the range given the parameters.
  b = 0;
  e = n;
  if (begin != null && b < begin) {
    b = begin;
  }
  if (end != null && end < e) {
    e = end;
    if (e < 0) e += n;
  }

  if (compare == null) {
    mergeSortDefault(list, b, e, threshold);
  } else {
    mergeSortCustom(list, b, e, threshold, compare);
  }
}