Implement Merge Sort and Return a Sorted Array

Problem Statement

Given an array of integers nums, sort the array in non-decreasing order using the Merge Sort algorithm from scratch and return the sorted array. You must not use any built-in sorting functions (such as Python's sort() or sorted()).

Your solution should follow the divide-and-conquer paradigm:

1. Recursively divide the array into two halves until subarrays contain at most one element.
2. Merge the sorted subarrays back together to produce the final sorted result.

Function Signature

def merge_sort(nums: list[int]) -> list[int]:
    pass

Constraints

• 0 <= len(nums) <= 10^5
• -10^9 <= nums[i] <= 10^9
• Expected Time Complexity: O(n log n) in best, average, and worst cases.
• Expected Auxiliary Space Complexity: O(n).

Examples

Example 1:

Input: nums = [5, 2, 3, 1]
Output: [1, 2, 3, 5]
Explanation: The array is divided into [5, 2] and [3, 1], recursively sorted to [2, 5] and [1, 3], and then merged into [1, 2, 3, 5].

Example 2:

Input: nums = [5, 1, 1, 2, 0, 0, -4]
Output: [-4, 0, 0, 1, 1, 2, 5]
Explanation: The algorithm correctly preserves duplicate elements and handles negative values.

Edge Cases to Consider

• An empty array ([]) should return [].
• A single-element array ([42]) should return [42].
• Arrays that are already sorted or sorted in reverse order.
• Arrays where all elements are identical.