• 1 ≤ nums.length ≤ 5 * 10⁴
• -5 * 10⁴ ≤ nums[i] ≤ 5 * 10⁴
• Space Complexity: O(N) for temporary arrays
• Time Complexity: O(N log N) guaranteed

Merge Sort is the classic example of the Divide and Conquer paradigm. While Quick Sort does the "hard work" during the partitioning (splitting) phase, Merge Sort does its heavy lifting during the Merge (combining) phase. The core insight is that it is computationally easier to merge two already-sorted lists than it is to sort one large, unsorted one.

The algorithm starts by taking the array and cutting it exactly in half. It then calls itself recursively on both halves. This process repeats until the array is broken down into single-element sub-arrays.
- A single element is, by definition, already sorted.
- This serves as our base case, where the recursion stops and the "merging" begins.

Once we have two sorted halves, we combine them into a single sorted result using a two-pointer approach:
1. We compare the first element of the Left half with the first element of the Right half.
2. We take the smaller element and place it into a temporary result array.
3. We move the pointer forward in the half from which we took the element.
4. We repeat this until one half is exhausted, then append all remaining elements from the other half.

Because we always pick the element from the Left half first when values are equal, Merge Sort is naturally stable—it preserves the original relative order of duplicate elements.

- Guaranteed Performance: Unlike Quick Sort, which can degrade to O(N^2) if the pivot selection is poor, Merge Sort is strictly O(N log N) in all cases (Best, Average, and Worst).
- Stability: It is the default choice when you need to maintain the order of equal elements (e.g., sorting a list of transactions by "Amount" without shuffling their original "Timestamp" order).
- Linked Lists: Because it accesses data sequentially rather than randomly, it is the most efficient algorithm for sorting linked lists where random access is expensive.

Avoid it when:
- Memory is limited: Merge Sort is not "in-place." It requires O(N) extra space to store the temporary merged arrays, which can be a bottleneck for extremely large datasets.

FUNCTION mergesort(arr):
    IF length < 2: RETURN arr
    mid = length / 2
    left = mergesort(arr[0...mid])
    right = mergesort(arr[mid...end])
    RETURN merge(left, right)

FUNCTION merge(left, right):
    result = []
    WHILE left and right both have elements:
        IF left[0] <= right[0]: 
            ADD left[0] to result
            REMOVE left[0]
        ELSE: 
            ADD right[0] to result
            REMOVE right[0]
    ADD remaining elements from either list to result

- Stability: Yes (equal elements preserve their relative order).
- In-Place: No (requires O(N) extra space).
- Time Complexity: O(N log N) guaranteed (best, average, and worst).