Tim Sort — Interview Preparation¶

Junior Questions¶

Middle Questions¶

Senior Questions¶

Professional Questions¶

Coding Challenges¶

Challenge 1: Count Natural Runs¶

Given an array, count the number of maximal ascending or strictly-descending runs (the same way TimSort would detect them).

Go¶

package main

import "fmt"

func CountRuns(arr []int) int {
    if len(arr) <= 1 {
        return len(arr)
    }
    count := 1
    i := 0
    for i < len(arr)-1 {
        j := i + 1
        if arr[j] < arr[i] {
            // descending — extend with strict <
            for j < len(arr) && arr[j] < arr[j-1] {
                j++
            }
        } else {
            // ascending — extend with <=
            for j < len(arr) && arr[j] >= arr[j-1] {
                j++
            }
        }
        if j < len(arr) {
            count++
        }
        i = j
    }
    return count
}

func main() {
    fmt.Println(CountRuns([]int{1, 2, 3, 4, 5}))       // 1
    fmt.Println(CountRuns([]int{5, 4, 3, 2, 1}))       // 1
    fmt.Println(CountRuns([]int{1, 2, 5, 4, 3, 6, 7})) // 3
    fmt.Println(CountRuns([]int{3, 3, 3, 3}))          // 1 (non-strict ascending)
}

Java¶

public class CountRuns {
    public static int countRuns(int[] arr) {
        if (arr.length <= 1) return arr.length;
        int count = 1, i = 0;
        while (i < arr.length - 1) {
            int j = i + 1;
            if (arr[j] < arr[i]) {
                while (j < arr.length && arr[j] < arr[j - 1]) j++;
            } else {
                while (j < arr.length && arr[j] >= arr[j - 1]) j++;
            }
            if (j < arr.length) count++;
            i = j;
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(countRuns(new int[]{1, 2, 3, 4, 5}));        // 1
        System.out.println(countRuns(new int[]{5, 4, 3, 2, 1}));        // 1
        System.out.println(countRuns(new int[]{1, 2, 5, 4, 3, 6, 7}));  // 3
        System.out.println(countRuns(new int[]{3, 3, 3, 3}));           // 1
    }
}

Python¶

def count_runs(arr):
    if len(arr) <= 1:
        return len(arr)
    count = 1
    i = 0
    while i < len(arr) - 1:
        j = i + 1
        if arr[j] < arr[i]:
            while j < len(arr) and arr[j] < arr[j - 1]:
                j += 1
        else:
            while j < len(arr) and arr[j] >= arr[j - 1]:
                j += 1
        if j < len(arr):
            count += 1
        i = j
    return count


if __name__ == "__main__":
    print(count_runs([1, 2, 3, 4, 5]))        # 1
    print(count_runs([5, 4, 3, 2, 1]))        # 1
    print(count_runs([1, 2, 5, 4, 3, 6, 7]))  # 3
    print(count_runs([3, 3, 3, 3]))           # 1

Why this matters in interviews: Run detection is the core of TimSort. Many interviewers ask for it as a warm-up before discussing the full algorithm.

Challenge 2: Stable Merge of Two Sorted Arrays¶

Implement a stable merge — equal elements from the left array come before equal elements from the right.

Go¶

package main

import "fmt"

func StableMerge(left, right []int) []int {
    out := make([]int, 0, len(left)+len(right))
    i, j := 0, 0
    for i < len(left) && j < len(right) {
        if left[i] <= right[j] { // <= for stability
            out = append(out, left[i])
            i++
        } else {
            out = append(out, right[j])
            j++
        }
    }
    out = append(out, left[i:]...)
    out = append(out, right[j:]...)
    return out
}

func main() {
    fmt.Println(StableMerge([]int{1, 3, 5}, []int{2, 4, 6}))
    fmt.Println(StableMerge([]int{1, 1, 1}, []int{1, 1, 1})) // [1 1 1 1 1 1] — order preserved
}

Java¶

import java.util.Arrays;

public class StableMerge {
    public static int[] merge(int[] left, int[] right) {
        int[] out = new int[left.length + right.length];
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) out[k++] = left[i++];
            else                      out[k++] = right[j++];
        }
        while (i < left.length)  out[k++] = left[i++];
        while (j < right.length) out[k++] = right[j++];
        return out;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(merge(new int[]{1, 3, 5}, new int[]{2, 4, 6})));
    }
}

Python¶

def stable_merge(left, right):
    out = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])
    out.extend(right[j:])
    return out


if __name__ == "__main__":
    print(stable_merge([1, 3, 5], [2, 4, 6]))
    print(stable_merge([1, 1, 1], [1, 1, 1]))

Challenge 3: Galloping Search¶

Implement gallop_right: given a sorted array and a key, find the first index strictly greater than the key using exponential then binary search.

Python¶

def gallop_right(arr, key, lo=0, hi=None):
    """First index in arr[lo:hi] strictly > key."""
    if hi is None:
        hi = len(arr)
    # Exponential phase
    offset = 1
    while lo + offset < hi and arr[lo + offset] <= key:
        offset *= 2
    # Binary search in [lo + offset/2, min(lo + offset, hi))
    left = lo + offset // 2 + 1
    right = min(lo + offset + 1, hi)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] <= key:
            left = mid + 1
        else:
            right = mid
    return left


arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
print(gallop_right(arr, 5))   # 3 (first index > 5)
print(gallop_right(arr, 20))  # 10 (off the end)

Why this matters: Galloping is the distinctive optimization that makes TimSort fast on dominated runs. Knowing it cold separates "I read about TimSort" from "I understand TimSort."

Whiteboard / Discussion Questions¶

1. Why doesn't Tim Sort use a single fixed minrun = 32? Because for non-power-of-2 n, fixed minrun leaves a small "orphan" run that unbalances the merge tree. Computing minrun based on n keeps the tree perfectly balanced.

2. If you had to pick one sort for a brand-new programming language, would you pick TimSort? Defensible answer: yes for object/general-purpose arrays (stability + adaptive), no for primitive arrays (pdqsort wins). Showing nuance is the point.

3. TimSort's worst-case complexity is O(n log n). Can you construct an input that hits this? Random data of length exactly 2^k for some k, with no natural runs longer than 1. Each pair must be merged, no galloping helps.

4. You're seeing Comparison method violates its general contract in production. How do you debug? Audit the comparator for transitivity (a < b ∧ b < c ⇒ a < c), totality (every pair must compare), and consistency (no mutable state). Common pitfall: a.value - b.value overflows for large int.

5. A coworker reimplemented TimSort and benchmarked it 2× slower than Arrays.sort. Why? Likely missing galloping (the biggest engineering win on real data), or using per-call allocations instead of one preallocated buffer, or weak minrun choice. The built-in has 20+ years of micro-optimization.

Common Follow-Up Tricks¶

• "What if comparisons are extremely expensive, like calling a remote service?" → Decorate-Sort-Undecorate: precompute keys once, sort by key. Tim Sort already minimizes comparisons via galloping, but DSU caps key cost at n.
• "What if the array is too big for RAM?" → External merge sort with TimSort as the chunk sort. See 02-merge-sort/senior.md.
• "How would you sort 10⁹ integers using TimSort?" → Don't. Use radix sort or pdqsort for primitives. TimSort's edge is stability + adaptive on object data.
• "Can you make TimSort in-place?" → Block merge sort variants exist (e.g., Kim and Kutzner's merge_inplace), but they're 2-3× slower in practice. Production TimSort always uses an auxiliary buffer.

Behavioral / System-Design Style¶

"Design a leaderboard service."¶

Most candidates jump to Redis sorted sets. A senior answer should connect to TimSort:

• The leaderboard backing store is rarely re-sorted from scratch — scores update incrementally.
• For periodic full-reorder operations (e.g., daily decay), TimSort excels because most positions don't change → many runs preserved → O(n + small) effective work.
• For top-k queries, heapq.nlargest(k, scores) is preferable to sorted(scores)[-k:] when k << n.

"How would you sort a feed of social media posts?"¶

• Posts arrive in time order → mostly sorted by created_at descending.
• A reverse-then-sort with TimSort runs in O(n) — detects the descending run, reverses, done.
• If sort key is "engagement" (not creation time), TimSort still wins because engagement correlates with recency → mostly-sorted input.

"Walk me through what happens when I call Collections.sort(myList)."¶

• Collections.sort delegates to List.sort(null).
• ArrayList.sort calls Arrays.sort on the backing array — TimSort.
• TimSort: detect runs → pad short runs with Binary Insertion → push onto stack → merge per invariants → final merge-force.
• If the list is a LinkedList, the backing array is copied first (O(n)), sorted, then copied back. Linked lists sort with extra O(n) work.
• Comparator: if null, uses Comparable.compareTo; else uses the provided Comparator.
• A non-transitive comparator throws IllegalArgumentException: Comparison method violates its general contract mid-sort.

One-Liner Trivia (Pop Quiz)¶