Tim Sort | DrawCode

1. One-Liner

Tim Sort is a hybrid stable algorithm that detects natural runs, sorts short runs with insertion sort, and merges runs using rules inspired by merge sort with galloping optimizations.

2. The Problem It Solves

Real-world data often contains long already-sorted chunks (runs). Tim Sort exploits this to approach O(n) on friendly inputs while keeping O(n log n) worst case and stability — used in Python and Java.

3. The Core Idea

Like merging newspaper sections that are already internally ordered: don’t reshuffle long ordered spans; only fix short gaps and then merge balanced run sizes.

4. How It Works (Step-by-Step)

Step	What Happens
1.	Scan array; classify ascending or strictly descending runs
2.	Reverse descending runs; if run shorter than minrun, extend with insertion sort
3.	Push runs on a stack maintaining invariants on run lengths (powers of two pattern)
4.	Merge adjacent runs; use galloping when one side wins many times in a row

5. Dry Run Example

Data with a long sorted middle: Tim identifies big runs, avoids redundant work, merges only what’s needed — fewer comparisons than plain merge on random data.

6. Key Properties

Property	Value
Stable	Yes
Adaptive	Excellent on partially ordered data
Worst case	O(`n log n`)

7. Where It Is Used

Company / System	How They Use It
Python `list.sort`, `sorted`	Default algorithm
Java `Arrays.sort` for objects	TimSort implementation
Android / many runtimes	Stable general-purpose sort

8. Interview Tips

Explain runs + minrun; why merge order matters for comparisons; contrast with Quick Sort (stability).

9. Comparison with Other Algorithms

Algorithm	Stable	Real data	Implementation
Tim Sort	Yes	Excellent	Complex
Merge Sort	Yes	Good	Simpler
Quick Sort	No	Fast avg	Simpler in-place

10. Complexity

Metric	Value
Time (Best)	O(`n`) on pre-sorted / single-run data
Time (Average)	O(`n log n`)
Time (Worst)	O(`n log n`)
Space	O(`n`) for merge buffers
Stable?	Yes

Implementation Example (PYTHON)

def tim_sort(arr):
    MIN_RUN = 32
    n = len(arr)
    for s in range(0, n, MIN_RUN):
        e = min(s + MIN_RUN, n)
        for i in range(s + 1, e):
            k = arr[i]
            j = i - 1
            while j >= s and arr[j] > k:
                arr[j + 1] = arr[j]
                j -= 1
            arr[j + 1] = k
    size = MIN_RUN
    while size < n:
        for lo in range(0, n, 2 * size):
            mid = min(lo + size, n)
            hi = min(lo + 2 * size, n)
            if mid < hi:
                _merge_slice(arr, lo, mid, hi)
        size *= 2
    return arr

def _merge_slice(a, lo, mid, hi):
    L, R = a[lo:mid], a[mid:hi]
    i = j = 0
    for k in range(lo, hi):
        if j >= len(R) or (i < len(L) and L[i] <= R[j]):
            a[k] = L[i]; i += 1
        else:
            a[k] = R[j]; j += 1