Implement merge sort and largest 1-rectangle

This challenge contains two independent tasks. Part 1: Implement Merge Sort Given an integer array nums, return a new array that contains exactly the same values as nums, arranged so that each element is no greater than the element after it. You must implement the merge sort algorithm yourself. You may not call a library routine that sorts the whole array in one step, such as sorted(nums) or nums.sort(). After writing the algorithm, state its worst-case time complexity and…