Explain the Recursion Tree of Merge Sort
SalesforceMember of Technical Staff · Onsite
Last updated
Explain the merge sort recursion tree from a five-element example through the general recurrence. Derive per-level work, uneven split height, Theta(n log n) time, merge-buffer space, call-stack depth, stability, and empty-input handling.
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?
Follow-up questions
- Why does merge sort keep its asymptotic running time on already sorted input?
- How do repeated values affect stability but not the recursion-tree shape?
- What extra allocation cost can arise if every recursive call copies slices?
- How does bottom-up merge sort change the control flow and stack usage?
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.