if using paper please print it nicely otherwise typing is fine. you can draw diagrams as well.

2. (advanced) Let's slightly tweak Merge Sort. Instead of partitioning the array into two subarrays, we will do into three subarrays of an (almost) equal size. Then, each recursive call will sort each subarray, and we will merge the three sorted subarrays. Assuming that merging can be done in O(n) time, write a recurrence for the running time of this new version of Merge Sort, and solve it