Explain the Recursion Tree of Merge Sort

# Explain the Recursion Tree of Merge Sort After implementing merge sort, explain its recursion tree in detail. Use the array `[5, 2, 4, 2, -1]` to show the subarray sizes at each split, the base cases, and where merge work occurs. Then generalize the tree for an input of length `n`. Derive the recurrence, explain the number of levels and the total work on each level, and give the time and auxiliary-space complexity. Address lengths that are not powers of two and the empty-array case. ### Clarifying Questions to Ask - Should the analysis include the cost of copying slices, or may the implementation use index ranges and one reusable buffer? - Should auxiliary space distinguish the merge buffer from the recursive call stack? - Is the empty array handled before recursion begins? - Does the requested tree show only split calls, or both split and merge work? ### What a Strong Answer Covers - Uses `T(n) = T(floor(n/2)) + T(ceil(n/2)) + Theta(n)` for uneven splits. - Shows that each nontrivial level processes a total of `Theta(n)` elements during merging. - Explains why the height is `ceil(log2 n)` up to the base-case convention. - Accounts for `n` one-element leaves and does not assume `n` is a power of two. - Derives `Theta(n log n)` time rather than stating it without the tree argument. - Separates `O(n)` merge storage from `O(log n)` recursive stack depth for an index-range implementation. - Handles `n = 0` before applying logarithmic reasoning. ### Follow-up Questions 1. Why does merge sort keep its asymptotic running time on already sorted input? 2. How do repeated values affect stability but not the recursion-tree shape? 3. What extra allocation cost can arise if every recursive call copies slices? 4. How does bottom-up merge sort change the control flow and stack usage?