Merge Sort

Intuition

Sorting a large array is hard, but merging two already-sorted lists is easy: walk both with a pair of pointers and always take the smaller front element. Merge sort leans on this by breaking the problem down until each piece is a single element (already sorted by definition), then combining pieces upward. Every level of the recursion touches all n elements once during the merge, and there are log n levels, giving the O(n log n) bound. It is also stable, meaning equal values keep their original relative order.

Algorithm walkthrough

1. 1If the array has one element or none, it is already sorted, so return it directly.
2. 2Split the array at its midpoint into a left part and a right part.
3. 3Recursively sort the left part and the right part.
4. 4Merge the two sorted parts by repeatedly appending the smaller of the two current front elements.
5. 5Append any leftover elements from whichever side was not exhausted and return the merged result.

Implementation

from typing import List


class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        if len(nums) <= 1:
            return nums
        mid = len(nums) // 2
        left = self.sortArray(nums[:mid])
        right = self.sortArray(nums[mid:])
        return self._merge(left, right)

    def _merge(self, left: List[int], right: List[int]) -> List[int]:
        merged = []
        i = j = 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[j])
                j += 1
        merged.extend(left[i:])
        merged.extend(right[j:])
        return merged