mergeSort<T extends Comparable> function

List<T> mergeSort<T extends Comparable>(List<T> list)

🧠 Merge Sort Algorithm

Sorts the input list using the Merge Sort algorithm, which is based on the divide-and-conquer paradigm. Merge Sort recursively divides the list into halves, sorts each half, and then merges the sorted halves.

Usage:

var arr = [38, 27, 43, 3, 9, 82, 10];
var sorted = mergeSort(arr); // [3, 9, 10, 27, 38, 43, 82]

• Time Complexity: O(n log n) for all cases
• Space Complexity: O(n) (not in-place)
• Stable sort

Implementation

List<T> mergeSort<T extends Comparable>(List<T> list) {
  if (list.length <= 1) return list;

  int mid = list.length ~/ 2;
  var left = mergeSort(list.sublist(0, mid));
  var right = mergeSort(list.sublist(mid));

  return _merge(left, right);
}