Sort an array of integers in non-decreasing order by implementing merge sort. Return a new sorted array and do not rely on Python's built-in sorting functions.
nums = [5, 2, 3, 1]Output[1, 2, 3, 5]WhyThe integers are reordered from smallest to largest.nums = [5, 1, 1, 2, 0, 0]Output[0, 0, 1, 1, 2, 5]WhyDuplicates remain in the result and appear in sorted order.`0 <= len(nums) <= 10^5``-10^9 <= nums[i] <= 10^9`Handle duplicates, negatives, and empty input correctly