Visualizing the Tim Sort algorithm in Flutter

1. What Is Tim Sort?

Tim Sort is a hybrid sorting algorithm that combines the best parts of Merge Sort and Insertion Sort. It was invented by Tim Peters in 2002 and is the default sorting algorithm in Python (.sort() and sorted()), and in Java for Arrays.sort() (for objects).

Tim Sort was designed for real-world datasets that often contain ordered sequences. It detects and exploits these naturally occurring runs for better efficiency.

2. How Tim Sort Works

Tim Sort works in three main steps:

Divide the array into small chunks (called runs) — usually 32–64 elements.
Sort each run using Insertion Sort (fast for small or nearly sorted arrays).
Merge runs together using Merge Sort.

If the input has ordered patterns, Tim Sort handles it extremely efficiently — much faster than other O(n log n) algorithms in practice.

3. Tim Sort Pseudocode

define MIN_RUN = 32

function timSort(array):
    n = length(array)

    # Sort small subarrays (runs) using Insertion Sort
    for i in range(0, n, MIN_RUN):
        insertionSort(array, i, min((i+MIN_RUN-1), (n-1)))

    # Merge runs in size powers of two
    size = MIN_RUN
    while size < n:
        for start in range(0, n, size * 2):
            mid = start + size - 1
            end = min(start + size * 2 - 1, n - 1)
            merge(array, start, mid, end)
        size = size * 2

4. Step-by-Step Example

Sort [5, 1, 4, 2, 8, 0, 2, 9, 7, 3]

Assume MIN_RUN = 4

Step 1: Split into runs (of 4 or less)

Runs:

[5, 1, 4, 2]
[8, 0, 2, 9]
[7, 3]

Step 2: Sort runs using Insertion Sort:

[1, 2, 4, 5]
[0, 2, 8, 9]
[3, 7]

Step 3: Merge runs using Merge Sort:

Merge [1, 2, 4, 5] and [0, 2, 8, 9] → [0, 1, 2, 2, 4, 5, 8, 9]
Merge with [3, 7] → [0, 1, 2, 2, 3, 4, 5, 7, 8, 9]

Final sorted array:

5. Time and Space Complexity

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

Space Complexity: O(n)
Stable Sort: Yes
Real-world performance: Excellent

6. Tim Sort in Dart (Flutter-Friendly)

const int MIN_RUN = 32;

Future<void> timSort(List<int> array, Function(List<int>) onUpdate) async {
  int n = array.length;

  // Insertion sort for small runs
  for (int i = 0; i < n; i += MIN_RUN) {
    await insertionSort(array, i, min(i + MIN_RUN - 1, n - 1), onUpdate);
  }

  // Merge runs
  for (int size = MIN_RUN; size < n; size *= 2) {
    for (int left = 0; left < n; left += 2 * size) {
      int mid = left + size - 1;
      int right = min((left + 2 * size - 1), (n - 1));
      if (mid < right) {
        await merge(array, left, mid, right, onUpdate);
      }
    }
  }
}

Future<void> insertionSort(List<int> arr, int left, int right, Function(List<int>) onUpdate) async {
  for (int i = left + 1; i <= right; i++) {
    int temp = arr[i];
    int j = i - 1;
    while (j >= left && arr[j] > temp) {
      arr[j + 1] = arr[j];
      j--;
      onUpdate(List.from(arr));
      await Future.delayed(Duration(milliseconds: 300));
    }
    arr[j + 1] = temp;
    onUpdate(List.from(arr));
    await Future.delayed(Duration(milliseconds: 300));
  }
}

Future<void> merge(List<int> arr, int l, int m, int r, Function(List<int>) onUpdate) async {
  List<int> left = arr.sublist(l, m + 1);
  List<int> right = arr.sublist(m + 1, r + 1);
  int i = 0, j = 0, k = l;

  while (i < left.length && j < right.length) {
    arr[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
    onUpdate(List.from(arr));
    await Future.delayed(Duration(milliseconds: 300));
  }

  while (i < left.length) {
    arr[k++] = left[i++];
    onUpdate(List.from(arr));
    await Future.delayed(Duration(milliseconds: 300));
  }

  while (j < right.length) {
    arr[k++] = right[j++];
    onUpdate(List.from(arr));
    await Future.delayed(Duration(milliseconds: 300));
  }
}

7. Visualization with Flutter + CustomPaint

Tim Sort provides a unique animation opportunity:

Highlight runs with distinct colors during Insertion Sort.
Animate merges step by step using CustomPaint.
Annotate the array visually with markers like “Run Start”, “Run End”, and “Merging…”
Color transitions can help show the transition from local sort to global merge.

8. When Should You Use Tim Sort?

Use Tim Sort when:

Your dataset has partial order or repeating patterns.
You need stable sorting.
You’re dealing with real-world application data (like strings, filenames, records).

It’s ideal for high-performance apps — many languages already use it under the hood!

9. Summary

Tim Sort is a modern, efficient, and real-world-ready sorting algorithm that smartly combines Insertion Sort and Merge Sort. Its optimization for partially sorted data gives it a real-world edge over traditional algorithms.

Great for education and perfect for production.

Next up: we’ll dive into the surprisingly elegant Shell Sort 🐚 — the first algorithm to break the quadratic time barrier!