Given an array of integers nums, return a new array containing the same elements sorted in non-decreasing order. Implement the sorting algorithm yourself using merge sort, and do not use Python's built-in sorting functions.
Example 1:
Input: nums = [5, 2, 3, 1]
Output: [1, 2, 3, 5]
Explanation: Merge sort splits the array, sorts each half, and merges them in order.
Example 2:
Input: nums = [5, 1, 1, 2, 0, 0]
Output: [0, 0, 1, 1, 2, 5]
Explanation: Duplicate values must be preserved and placed in sorted order.
1 <= len(nums) <= 10^5-10^9 <= nums[i] <= 10^9sorted() or list.sort()