Both remaining halves are sorted. The problem divides evenly, and two sorted sequences can be combined with a linear two-pointer scan.

A merge is a proof step: the smallest remaining value must be at one of the two fronts. Take it, preserve both halves’ sorted invariant, and repeat.

What the function promises: Return a stable sorted list. The input is not mutated. Equal items from the left half keep precedence.

def merge_sort(values):
    if len(values) < 2:
        return list(values)
    middle = len(values) // 2
    left, right = merge_sort(values[:middle]), merge_sort(values[middle:])
    answer = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            answer.append(left[i]); i += 1
        else:
            answer.append(right[j]); j += 1
    return answer + left[i:] + right[j:]

assert merge_sort([4,1,3,2,1]) == [1,1,2,3,4]
assert merge_sort([]) == []

Work and storage: O(n log n) time and O(n) auxiliary storage here, plus O(log n) recursion depth.

When to recognize it: The problem divides evenly, and two sorted sequences can be combined with a linear two-pointer scan.

Check before applying it: Recursive slicing creates extra copies; linked lists and arrays need different practical merge mechanics.

Skip recursive splitting and perform a k-way merge with a heap.