Implement Merge Sort and Explain Its Recursion Tree

Write a complete implementation of merge sort that sorts an array of integers into non‑decreasing order. You must build the algorithm from scratch — no library sorting routines. After implementing the algorithm, analyze the recursion tree that merge sort creates and answer these three questions: For each depth level of the recursion tree, what is the total number of elements across all subproblems at that level? How many distinct levels does the recursion tree contain?…