Merge Sort

Escaping the O(n²) Adjacent-Swap Bottleneck

Every algorithm that only swaps adjacent elements (Bubble, Insertion, Gnome Sort) fixes at most one inversion per swap. Because a reversed array has n(n - 1) / 2 inversions, any adjacent-swap sort is mathematically trapped in Ω(n²) worst-case time.

Merge Sort jumps elements across half the array in a single comparison by exploiting one clean observation: given two sorted lists L and R, the smallest element of L ∪ R must sit at either L[0] or R[0].

1. Divide: Split nums at mid = len(nums) // 2 until subarrays reach length ≤ 1 (trivially sorted).
2. Conquer & Merge: Advance pointers i across L and j across R, appending min(L[i], R[j]) at each step in O(|L| + |R|) time.

Visual Recursion Tree (T(n) = 2T(n/2) + O(n))

• Level 0: 1 merge of size n → O(n) work
• Level 1: 2 merges of size n/2 → O(n) total work
• Level k: 2ᵏ merges of size n / 2ᵏ → O(n) total work

With log₂ n levels × O(n) work per level, total time is Θ(n log n) regardless of whether the input is sorted, random, or adversarial!

Clean Python Implementation

def merge_sort(nums: list[int]) -> list[int]:
    """Stable Θ(n log n) Merge Sort returning a new sorted list."""
    if len(nums) <= 1:
        return nums[:]

    mid = len(nums) // 2
    left = merge_sort(nums[:mid])
    right = merge_sort(nums[mid:])
    return _merge(left, right)


def _merge(left: list[int], right: list[int]) -> list[int]:
    merged: list[int] = []
    i = j = 0

    while i < len(left) and j < len(right):
        # '<=' picks left[i] on ties, guaranteeing stability
        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

Where Merge Sort Powers Production Infrastructure

• Timsort (Python list.sort() / Java Arrays.sort): Detects natural ascending/descending runs, pads short runs via Insertion Sort, and merges runs with galloping binary search.
• External Sorting & LSM Tree Compaction: When 500 GB of data exceeds RAM, databases sort memory-sized chunks into SSTables and stream them together via k-way heap merge!