Visualizing the Merge Sort algorithm in Flutter

1. What Is Merge Sort?

Merge Sort is a divide-and-conquer sorting algorithm. It works by:

1. Recursively dividing the array into halves,
2. Sorting each half, and
3. Merging the sorted halves back together.

Merge Sort is known for its guaranteed O(n log n) performance, stability, and ease of implementation for linked structures and large datasets — but it’s not in-place, requiring extra space.

---

2. How Merge Sort Works

Here’s the process:

1. Divide the array in half.
2. Recursively sort each half.
3. Merge the sorted halves together.

This recursion continues until each subarray has just one element (which is trivially sorted).

Merge Step

Merging is the key operation. It compares the smallest unmerged elements of two sorted subarrays and places the smaller one into the result array — preserving order (hence, stable).

---

3. Merge Sort Pseudocode

mergeSort(array):
    if array has 1 or 0 elements:
        return array

    mid = length(array) / 2
    left = mergeSort(array[0...mid])
    right = mergeSort(array[mid...end])

    return merge(left, right)

merge(left, right):
    result = []
    while both arrays have elements:
        if left[0] <= right[0]:
            result.append(left.removeFirst())
        else:
            result.append(right.removeFirst())

    append any remaining elements from left or right
    return result

---

4. Step-by-Step Example

Sorting [6, 3, 8, 5, 2]

Step 1: Divide

[6, 3, 8, 5, 2]
→ [6, 3] and [8, 5, 2]
→ [6], [3], [8], [5], [2]

Step 2: Merge Back

• Merge [6] and [3] → [3, 6]
• Merge [5] and [2] → [2, 5]
• Merge [8] and [2, 5] → [2, 5, 8]
• Merge [3, 6] and [2, 5, 8] → [2, 3, 5, 6, 8]

---

5. Time and Space Complexity

Case	Time Complexity
Best	O(n log n)
Average	O(n log n)
Worst	O(n log n)

• Space Complexity: O(n) (not in-place)
• Stable Sort: Yes

---

6. Merge Sort in Dart (Flutter-Friendly)

Future<List<int>> mergeSort(
  List<int> array,
  Function(List<int>) onUpdate,
) async {
  if (array.length <= 1) return array;

  int mid = array.length ~/ 2;
  List<int> left = await mergeSort(array.sublist(0, mid), onUpdate);
  List<int> right = await mergeSort(array.sublist(mid), onUpdate);

  return await _merge(left, right, onUpdate);
}

Future<List<int>> _merge(
  List<int> left,
  List<int> right,
  Function(List<int>) onUpdate,
) async {
  List<int> result = [];
  int i = 0, j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.add(left[i++]);
    } else {
      result.add(right[j++]);
    }
    onUpdate(List.from(result + left.sublist(i) + right.sublist(j)));
    await Future.delayed(Duration(milliseconds: 300));
  }

  while (i < left.length) {
    result.add(left[i++]);
    onUpdate(List.from(result + left.sublist(i) + right.sublist(j)));
    await Future.delayed(Duration(milliseconds: 300));
  }

  while (j < right.length) {
    result.add(right[j++]);
    onUpdate(List.from(result + left.sublist(i) + right.sublist(j)));
    await Future.delayed(Duration(milliseconds: 300));
  }

  return result;
}

---

7. Visualization with Flutter + CustomPaint

Visual Cues:

• Highlight splits recursively — imagine horizontal lines slicing the array.
• During merging:
  • Draw two arrays converging into a third.
  • Animate comparisons and placements step-by-step.
  • Fade out merged parts and highlight remaining elements.

You can even represent each recursive level as a stack of bars vertically.

---

8. When Should You Use Merge Sort?

Merge Sort is ideal when:

• You need stable sorting.
• You’re sorting linked lists.
• Predictable performance is more important than in-place efficiency.
• You’re working with external sorting (like large files).

---

9. Summary

Merge Sort is a balanced, reliable, and elegant sorting algorithm. Though it uses more memory, its divide-and-conquer strategy guarantees good performance and is especially suited to recursive or linked data structures.

It divides to conquer — and conquers with consistency.