Given an integer array nums, sort it in non-decreasing order using the Merge Sort algorithm, implemented recursively. Divide the array into halves, sort each half recursively, and merge the two sorted halves. Return the sorted array.
Input: An integer array nums.
Output: Return the sorted array as [v1,v2,...].
Input: [5,2,3,1,4]
Output: [1,2,3,4,5]
Explanation: Classical merge sort output.Input: [3,2,1]
Output: [1,2,3]
Explanation: Reverse-sorted input.Input: [1]
Output: [1]
Explanation: Single element sorted.1 <= nums.length <= 100-10^9 <= nums[i] <= 10^9