Merge Sort Algorithm

# Merge Sort is a divide-and-conquer algorithm that:
# 1. Divides array into two halves
# 2. Recursively sorts both halves
# 3. Merges the two sorted halves
#
# Time Complexity: O(n log n) - always
# Space Complexity: O(n) - requires auxiliary array for merging
# Stable: Yes - maintains relative order of equal elements
# In-place: No - requires extra space

class Solution:
    def mergeSort(self, nums: List[int]) -> List[int]:
        # Base case
        if len(nums) <= 1:
            return nums

        # Divide
        mid = len(nums) // 2
        left = self.mergeSort(nums[:mid])
        right = self.mergeSort(nums[mid:])

        # Conquer: Merge sorted halves
        return self.merge(left, right)

    def merge(self, left: List[int], right: List[int]) -> List[int]:
        """Merge two sorted arrays into one sorted array"""
        result = []
        i = j = 0

        # Compare elements from both arrays
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1

        # Append remaining elements
        result.extend(left[i:])
        result.extend(right[j:])

        return result

    # In-place version (modifies original array)
    def mergeSortInPlace(self, nums: List[int]) -> None:
        """Sort array in-place using merge sort"""
        if len(nums) <= 1:
            return

        def mergeSortHelper(arr, left, right):
            if left >= right:
                return

            mid = (left + right) // 2
            mergeSortHelper(arr, left, mid)
            mergeSortHelper(arr, mid + 1, right)
            mergeInPlace(arr, left, mid, right)

        def mergeInPlace(arr, left, mid, right):
            # Create temp arrays
            left_arr = arr[left:mid + 1]
            right_arr = arr[mid + 1:right + 1]

            i = j = 0
            k = left

            while i < len(left_arr) and j < len(right_arr):
                if left_arr[i] <= right_arr[j]:
                    arr[k] = left_arr[i]
                    i += 1
                else:
                    arr[k] = right_arr[j]
                    j += 1
                k += 1

            while i < len(left_arr):
                arr[k] = left_arr[i]
                i += 1
                k += 1

            while j < len(right_arr):
                arr[k] = right_arr[j]
                j += 1
                k += 1

        mergeSortHelper(nums, 0, len(nums) - 1)

# Merge Sort Properties:
# ✓ Stable (preserves order of equal elements)
# ✓ Guaranteed O(n log n) time
# ✓ Good for linked lists (no random access needed)
# ✗ Not in-place (needs O(n) extra space)
# ✗ Slower than quicksort in practice for arrays
#
# When to use Merge Sort:
# 1. Need guaranteed O(n log n) time (no O(n^2) worst case)
# 2. Need stable sorting
# 3. Sorting linked lists (natural fit)
# 4. External sorting (data doesn't fit in memory)