Merge Sort

Problem

Rendering a leaderboard, ranking log entries by timestamp, or ordering search results by relevance all reduce to the same primitive: sort a list of numbers. Library sorts hide the algorithm, but interviews ask you to build it. Implement merge sort: given an array of integers, return a new array with the same values sorted in ascending order. The sort must be stable (equal values keep their original relative order) and must not mutate the input.

Example 1:

Input: [6, 3, 8, 1]
Output: [1, 3, 6, 8]

Example 2:

Input: [4, 2, -3, 5, 9, 0]
Output: [-3, 0, 2, 4, 5, 9]
Explanation: Negative values sort before non-negative ones.

Example 3:

Input: []
Output: []

Constraints:

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

Solution Breakdown

Approach - divide and conquer: split at the midpoint, sort each half recursively, merge the sorted halves.

The recursion bottoms out at length 0 or 1, where a list is trivially sorted - that is the entire base case. The real work happens in the merge step: given two sorted halves, scan both with an index pointer each, and every iteration appends the smaller of the two front elements to the result. Because both halves are sorted, each comparison retires exactly one element, so merging lists of size m and k costs O(m + k). There are O(log n) levels of recursion (the array halves each level) and O(n) total merge work per level (every element participates in exactly one merge per level), which gives the recurrence T(n) = 2T(n/2) + O(n) and solves to O(n log n).

Stability comes from one character: the merge comparison is left[i] <= right[j], not <. On a tie the element from the left half goes first, and the left half's elements always appeared earlier in the original array, so equal values keep their original relative order through every level. Trace [6, 3, 8, 1]: split into [6] and [3, 8, 1]; the right half splits into [3] and [8, 1], which splits into [8] and [1] and merges to [1, 8]; then [3] and [1, 8] merge to [1, 3, 8]; finally [6] and [1, 3, 8] merge to [1, 3, 6, 8]. The function returns a new list built from slice copies, so the input is never mutated.

Edge cases - empty list and single element are handled by the len(nums) <= 1 base case with no special-casing; duplicates like [2, 2, 5, 2] sort correctly because the split is positional, not value-based, and the <= merge keeps duplicate order stable.

Complexity - O(n log n) time in all cases (best, average, worst - the split is always at the midpoint, so input values cannot unbalance it), O(n) auxiliary space for the merge buffer plus O(log n) recursion stack.