Merge Sort (Top-Down)

Split the array recursively, sort each half, then merge two sorted runs into one sorted result.

Algorithm

Basic Implementation

basic.dart

List<int> mergeSort(List<int> values) {
  if (values.length <= 1) return values;
  final mid = values.length ~/ 2;
  final left = mergeSort(values.sublist(0, mid));
  final right = mergeSort(values.sublist(mid));
  final merged = <int>[];
  var i = 0;
  var j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      merged.add(left[i++]);
    } else {
      merged.add(right[j++]);
    }
  }
  merged.addAll(left.sublist(i));
  merged.addAll(right.sublist(j));
  return merged;
}

void main() {
  final arr = <int>[5, 1, 4, 2, 8];
  print(mergeSort(arr));
}

The pinned input is [5, 1, 4, 2, 8]. The diagrams show the split into recursive halves, the sorted subarrays, and the final merge choices.

Step 1 - Split the input

The first midpoint splits [5, 1, 4, 2, 8] into left [5, 1] and right [4, 2, 8].

Step 2 - Sorted halves return

Recursive calls return [1, 5] and [2, 4, 8] before the final merge begins.

Step 3 - Merge by taking smaller fronts

Take 1 from left, then 2 and 4 from right, then the remaining 5 and 8.

Complexity

Time: O(n log n)
Space: O(n)
Stable: yes

Implementation notes

Keep the explicit algorithmic steps instead of calling a standard-library sort. The replay is meant to expose comparisons, movement, and recursion.
The implementation is intentionally compact for learning and replay, not a production sorting utility.

divide and conquer Each recursive call solves a smaller sorted subproblem.

merge step Two sorted halves are combined by repeatedly taking the smaller front item.