Sort an integer array in non-decreasing order by implementing merge sort yourself. Return a new sorted array and do not use built-in sorting functions.
nums = [5, 2, 3, 1]Output[1, 2, 3, 5]WhySplit, sort each half, then merge.nums = [5, 1, 1, 2, 0, 0]Output[0, 0, 1, 1, 2, 5]WhyDuplicates remain and appear in sorted order.`1 <= len(nums) <= 10^5``-10^9 <= nums[i] <= 10^9`Do not use `sorted()` or `list.sort()`