🔄 Merge Sort Fundamentals

🎯 What is Merge Sort?

Merge Sort is a classic divide-and-conquer sorting algorithm. It divides the input array into two halves, recursively sorts each half, and then merges the two sorted halves back together. Invented by John von Neumann in 1945, it guarantees O(n log n) time complexity in all cases.

Time: O(n log n) | Space: O(n) | Stable: ✅ | Not In-Place

Deep Explanation

Divide and Conquer: Merge Sort follows three steps: Divide — split array into two halves; Conquer — recursively sort each half; Combine — merge the two sorted halves into a single sorted array.

Why it's important: Merge Sort is the foundation of external sorting (sorting data that doesn't fit in RAM), used in databases and big data systems. It's also the go-to example for analyzing recurrence relations: T(n) = 2T(n/2) + O(n).

📌 Divide & Conquer📌 Stable Sort📌 O(n log n) Guaranteed📌 External Sorting Ready

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    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
    result.extend(left[i:])
    result.extend(right[j:])
    return result

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# Output: [3, 9, 10, 27, 38, 43, 82]

📐 Divide & Conquer Walkthrough

🎯 Recursive Tree Example: [38, 27, 43, 3, 9, 82, 10]

Divide: [38,27,43,3] | [9,82,10]
Further Divide: [38,27] | [43,3] | [9,82] | [10]
Base: Single elements [38], [27], [43], [3], [9], [82], [10]
Merge: [27,38] | [3,43] | [9,82] | [10]
Merge: [3,27,38,43] | [9,10,82]
Final Merge: [3,9,10,27,38,43,82]

Recursion Depth

The recursion tree has height log₂(n), and at each level we do O(n) work merging. This gives the O(n log n) complexity.

⏱️ Time & Space Complexity

🎯 Complexity Analysis

Best-case: O(n log n) — already sorted array still requires merging
Worst-case: O(n log n) — always divides and merges fully
Average-case: O(n log n) — consistent performance
Space Complexity: O(n) — temporary arrays for merging

Recurrence Relation Derivation

T(n) = 2T(n/2) + O(n). Using Master Theorem: a=2, b=2, f(n)=O(n). Since f(n) = Θ(n^log₂²) = Θ(n), we get T(n) = Θ(n log n).

🔗 The Merge Process Deep Dive

🎯 Two-Pointer Merging

Merge operation uses two pointers to traverse two sorted arrays, always picking the smaller element. This is the key to Merge Sort's linear-time combine step.

def merge_with_details(left, right):
    """Visualized merge process"""
    result = []
    i = j = 0
    print(f"Merging {left} and {right}")
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            print(f"  Pick {left[i]} from left")
            i += 1
        else:
            result.append(right[j])
            print(f"  Pick {right[j]} from right")
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    print(f"  Result: {result}")
    return result

💻 Multiple Implementations

# In-place modification version (uses auxiliary array)
def merge_sort_inplace(arr, left=0, right=None, temp=None):
    if right is None:
        right = len(arr) - 1
        temp = [0] * len(arr)
    if left < right:
        mid = (left + right) // 2
        merge_sort_inplace(arr, left, mid, temp)
        merge_sort_inplace(arr, mid + 1, right, temp)
        merge_halves(arr, left, mid, right, temp)
    return arr

def merge_halves(arr, left, mid, right, temp):
    i, j, k = left, mid + 1, left
    while i <= mid and j <= right:
        if arr[i] <= arr[j]:
            temp[k] = arr[i]; i += 1
        else:
            temp[k] = arr[j]; j += 1
        k += 1
    while i <= mid:
        temp[k] = arr[i]; i += 1; k += 1
    while j <= right:
        temp[k] = arr[j]; j += 1; k += 1
    for idx in range(left, right + 1):
        arr[idx] = temp[idx]

🔄 Iterative (Bottom-Up) Merge Sort

🎯 Non-Recursive Approach

Bottom-up merge sort avoids recursion by iteratively merging subarrays of sizes 1, 2, 4, 8, ...

def bottom_up_merge_sort(arr):
    n = len(arr)
    temp = [0] * n
    width = 1
    while width < n:
        for left_start in range(0, n, 2 * width):
            mid = min(left_start + width - 1, n - 1)
            right_end = min(left_start + 2 * width - 1, n - 1)
            if mid < right_end:
                merge_ranges(arr, left_start, mid, right_end, temp)
        width *= 2
    return arr

def merge_ranges(arr, left, mid, right, temp):
    i, j, k = left, mid + 1, left
    while i <= mid and j <= right:
        if arr[i] <= arr[j]:
            temp[k] = arr[i]; i += 1
        else:
            temp[k] = arr[j]; j += 1
        k += 1
    while i <= mid: temp[k] = arr[i]; i += 1; k += 1
    while j <= right: temp[k] = arr[j]; j += 1; k += 1
    for idx in range(left, right + 1):
        arr[idx] = temp[idx]

📊 Step-by-Step Visualization

🎯 Example: [8, 3, 5, 1, 9, 2]

Divide: [8,3,5] | [1,9,2]
Divide left: [8,3] | [5] → merge: [3,8] then merge with [5] → [3,5,8]
Divide right: [1,9] | [2] → merge: [1,9] then merge with [2] → [1,2,9]
Final merge: [3,5,8] + [1,2,9] = [1,2,3,5,8,9]

🛡️ Stability & Properties

🎯 Merge Sort is Stable

Merge Sort preserves the relative order of equal elements because the merge operation picks from the left subarray when elements are equal (left[i] <= right[j]). This is essential for multi-key sorting.

Stable Sorting Example

When sorting [(2,'A'), (1,'B'), (2,'C')] by the first key, stable sort ensures (2,'A') comes before (2,'C') in the final result.

📈 Comparison with Other Sorts

vs Quick Sort: Merge Sort is stable and has guaranteed O(n log n); Quick Sort is faster in practice but O(n²) worst-case.
vs Heap Sort: Both O(n log n), but Merge Sort is stable and has better cache locality for merging.
vs Timsort (Python's sort): Timsort is a hybrid of Merge Sort and Insertion Sort.
vs Bubble/Insertion: Merge Sort vastly outperforms O(n²) sorts for large datasets.

⚡ Optimizations & Variations

Insertion Sort for Small Subarrays: For n < 15-20, insertion sort is faster
Check if Already Sorted: Skip merge if last element of left <= first of right
Iterative Bottom-Up: Reduces recursion overhead
Timsort: Python's built-in sort — detects runs and uses galloping merge

def optimized_merge_sort(arr, threshold=15):
    if len(arr) <= threshold:
        return insertion_sort(arr)  # Small subarray optimization
    mid = len(arr) // 2
    left = optimized_merge_sort(arr[:mid], threshold)
    right = optimized_merge_sort(arr[mid:], threshold)
    # Check if already merged
    if left[-1] <= right[0]:
        return left + right
    return merge(left, right)

🚀 Parallel Merge Sort

🎯 Divide & Conquer Parallelism

Merge Sort's divide step can be parallelized using threads or processes, making it ideal for multi-core systems.

from concurrent.futures import ThreadPoolExecutor
import threading

def parallel_merge_sort(arr, depth=0, max_depth=4):
    if len(arr) <= 1:
        return arr
    if depth >= max_depth:
        return merge_sort(arr)  # Fallback to sequential
    mid = len(arr) // 2
    with ThreadPoolExecutor(max_workers=2) as executor:
        left_future = executor.submit(parallel_merge_sort, arr[:mid], depth+1, max_depth)
        right_future = executor.submit(parallel_merge_sort, arr[mid:], depth+1, max_depth)
        left = left_future.result()
        right = right_future.result()
    return merge(left, right)

💾 In-Place Merge Sort Variant

🎯 Reducing Space to O(log n)

True in-place merge sort is complex (using rotations). The standard in-place merge sort still uses O(log n) stack space or O(n) auxiliary.

def inplace_merge_sort(arr, l, r):
    if l < r:
        mid = (l + r) // 2
        inplace_merge_sort(arr, l, mid)
        inplace_merge_sort(arr, mid + 1, r)
        inplace_merge(arr, l, mid, r)

def inplace_merge(arr, l, mid, r):
    # Using block swapping (O(1) extra space but O(n²) time)
    i, j = l, mid + 1
    while i <= mid and j <= r:
        if arr[i] <= arr[j]:
            i += 1
        else:
            val = arr[j]
            for k in range(j, i, -1):
                arr[k] = arr[k - 1]
            arr[i] = val
            i += 1; mid += 1; j += 1

🔗 Sorting Linked Lists with Merge Sort

🎯 Why Merge Sort is Perfect for Linked Lists

Merge Sort is the preferred algorithm for sorting linked lists because it requires O(1) extra space (just rearranging pointers) and has predictable performance.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val; self.next = next

def sort_linked_list(head):
    if not head or not head.next:
        return head
    mid = get_middle(head)
    right = mid.next
    mid.next = None
    left_sorted = sort_linked_list(head)
    right_sorted = sort_linked_list(right)
    return merge_lists(left_sorted, right_sorted)

def get_middle(head):
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

def merge_lists(l1, l2):
    dummy = ListNode(0)
    tail = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            tail.next = l1; l1 = l1.next
        else:
            tail.next = l2; l2 = l2.next
        tail = tail.next
    tail.next = l1 or l2
    return dummy.next

💪 Practice & Problem Patterns

🎯 Common Merge Sort Based Problems

Count Inversions: Count pairs (i,j) where i arr[j] — O(n log n) using merge sort
Sort an Almost Sorted Array: Using merge sort's adaptability
External Sorting: Sorting large files (multi-way merge)
LeetCode 912 (Sort an Array): Standard merge sort implementation
LeetCode 148 (Sort List): Linked list merge sort
LeetCode 315 (Count of Smaller Numbers After Self): Modified merge sort

def count_inversions(arr):
    """Count inversions using merge sort"""
    def merge_and_count(arr, temp, left, right):
        if left >= right: return 0
        mid = (left + right) // 2
        inv_count = merge_and_count(arr, temp, left, mid)
        inv_count += merge_and_count(arr, temp, mid + 1, right)
        inv_count += merge_and_count_split(arr, temp, left, mid, right)
        return inv_count
    
    def merge_and_count_split(arr, temp, left, mid, right):
        i, j, k = left, mid + 1, left
        inv_count = 0
        while i <= mid and j <= right:
            if arr[i] <= arr[j]:
                temp[k] = arr[i]; i += 1
            else:
                temp[k] = arr[j]; j += 1
                inv_count += (mid - i + 1)
            k += 1
        while i <= mid:
            temp[k] = arr[i]; i += 1; k += 1
        while j <= right:
            temp[k] = arr[j]; j += 1; k += 1
        for idx in range(left, right + 1):
            arr[idx] = temp[idx]
        return inv_count
    
    temp = [0] * len(arr)
    return merge_and_count(arr, temp, 0, len(arr) - 1)

print(count_inversions([8, 4, 2, 1]))  # Output: 6