Merge Sort Deep Dive: Divide, Conquer, and Count

Merge sort is the poster child of divide and conquer. Split the array in half, sort each half recursively, and merge the two sorted halves back together. It guarantees O(n log n) time in the worst case — no matter what the input looks like — which makes it the go-to when you need predictable performance.

---

1. The Divide and Conquer Strategy

Divide and conquer solves a problem by:

1. Divide: break the problem into smaller subproblems.
2. Conquer: solve each subproblem recursively.
3. Combine: merge the solutions of subproblems into the final answer.

For merge sort:

• Divide: split the array into two halves.
• Conquer: recursively sort each half.
• Combine: merge the two sorted halves into one sorted array.

---

2. The Merge Procedure

The heart of merge sort is the merge function. Given two sorted arrays, produce one sorted array in O(n) time.

def merge(left, right):
    """
    Merge two sorted arrays into one sorted array.

    Time: O(n) where n = len(left) + len(right)
    Space: O(n)
    """
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # <= ensures stability
            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


print(merge([1, 3, 5], [2, 4, 6]))  # [1, 2, 3, 4, 5, 6]
print(merge([1, 1, 2], [1, 3]))     # [1, 1, 1, 2, 3]

Why <= instead of <? Using <= keeps equal elements in their original relative order, making merge sort stable.

---

3. Recursive Merge Sort

def merge_sort(arr):
    """
    Sort an array using merge sort.

    Time: O(n log n) — always
    Space: O(n) — for the temporary arrays during merge

    Returns a new sorted array (does not modify input).
    """
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)


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

print(merge_sort([5, 4, 3, 2, 1]))
# Output: [1, 2, 3, 4, 5]

print(merge_sort([1]))
# Output: [1]

print(merge_sort([]))
# Output: []

---

4. In-Place Merge Sort (Index-Based)

The version above creates many temporary arrays. Here is a version that sorts in-place using indices:

def merge_sort_inplace(arr):
    """
    In-place merge sort using auxiliary array.

    Modifies arr in place.
    Time: O(n log n)
    Space: O(n) for the auxiliary array
    """
    if len(arr) <= 1:
        return

    aux = arr[:]  # auxiliary array

    def _merge_sort(lo, hi):
        """Sort arr[lo..hi] inclusive."""
        if lo >= hi:
            return

        mid = (lo + hi) // 2
        _merge_sort(lo, mid)
        _merge_sort(mid + 1, hi)
        _merge(lo, mid, hi)

    def _merge(lo, mid, hi):
        """Merge arr[lo..mid] and arr[mid+1..hi]."""
        # Copy to auxiliary array
        for k in range(lo, hi + 1):
            aux[k] = arr[k]

        i = lo
        j = mid + 1

        for k in range(lo, hi + 1):
            if i > mid:
                arr[k] = aux[j]
                j += 1
            elif j > hi:
                arr[k] = aux[i]
                i += 1
            elif aux[i] <= aux[j]:
                arr[k] = aux[i]
                i += 1
            else:
                arr[k] = aux[j]
                j += 1

    _merge_sort(0, len(arr) - 1)


data = [38, 27, 43, 3, 9, 82, 10]
merge_sort_inplace(data)
print(data)  # [3, 9, 10, 27, 38, 43, 82]

---

5. Bottom-Up Merge Sort (Iterative)

Instead of recursively splitting, you can merge bottom-up: start with subarrays of size 1, merge into size 2, then size 4, and so on.

def merge_sort_bottom_up(arr):
    """
    Iterative (bottom-up) merge sort.

    Time: O(n log n)
    Space: O(n)
    """
    n = len(arr)
    if n <= 1:
        return arr

    # Work with a temporary array
    temp = arr[:]
    size = 1

    while size < n:
        for lo in range(0, n, 2 * size):
            mid = min(lo + size, n)
            hi = min(lo + 2 * size, n)

            # Merge arr[lo..mid) and arr[mid..hi)
            left = temp[lo:mid]
            right = temp[mid:hi]

            i = j = 0
            k = lo
            while i < len(left) and j < len(right):
                if left[i] <= right[j]:
                    temp[k] = left[i]
                    i += 1
                else:
                    temp[k] = right[j]
                    j += 1
                k += 1
            while i < len(left):
                temp[k] = left[i]
                i += 1
                k += 1
            while j < len(right):
                temp[k] = right[j]
                j += 1
                k += 1

        size *= 2

    return temp


print(merge_sort_bottom_up([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]

Advantage: no recursion stack, which matters for very large arrays in languages with limited stack depth.

---

6. Counting Inversions Using Merge Sort

An inversion is a pair (i, j) where i < j but arr[i] > arr[j]. The number of inversions measures how “unsorted” an array is.

Brute force counts inversions in O(n^2). Merge sort does it in O(n log n) by counting during the merge step.

def count_inversions(arr):
    """
    Count the number of inversions in an array using merge sort.

    An inversion is a pair (i, j) where i < j and arr[i] > arr[j].

    Time: O(n log n)
    Space: O(n)

    Returns: (sorted_array, inversion_count)
    """
    if len(arr) <= 1:
        return arr, 0

    mid = len(arr) // 2
    left, left_inv = count_inversions(arr[:mid])
    right, right_inv = count_inversions(arr[mid:])

    merged = []
    inversions = left_inv + right_inv
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            # left[i] > right[j] means left[i], left[i+1], ..., left[-1]
            # are all greater than right[j] — that's len(left) - i inversions
            merged.append(right[j])
            inversions += len(left) - i
            j += 1

    merged.extend(left[i:])
    merged.extend(right[j:])

    return merged, inversions


arr = [2, 4, 1, 3, 5]
sorted_arr, inv_count = count_inversions(arr)
print(f"Sorted: {sorted_arr}, Inversions: {inv_count}")
# Inversions: (2,1), (4,1), (4,3) = 3

arr2 = [5, 4, 3, 2, 1]
_, inv_count2 = count_inversions(arr2)
print(f"Inversions in reverse sorted: {inv_count2}")  # 10 = 5*4/2

Why it works: when we pick right[j] over left[i], every remaining element in left (from index i to end) forms an inversion with right[j]. This is the key insight.

---

7. Merge Sort on Linked Lists

Merge sort is particularly well-suited for linked lists because:

• Finding the middle is O(n) via slow/fast pointers (no random access needed for the split).
• Merging two sorted linked lists is O(n) with O(1) extra space (just re-link nodes).
• No auxiliary array needed.

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


def merge_sort_linked_list(head):
    """
    LeetCode 148: Sort List.

    Sort a linked list using merge sort.

    Time: O(n log n)
    Space: O(log n) for recursion stack
    """
    # Base case
    if not head or not head.next:
        return head

    # Find the middle using slow/fast pointers
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # Split the list
    mid = slow.next
    slow.next = None

    # Recursively sort both halves
    left = merge_sort_linked_list(head)
    right = merge_sort_linked_list(mid)

    # Merge the two sorted halves
    return merge_linked_lists(left, right)


def merge_linked_lists(l1, l2):
    """Merge two sorted linked lists."""
    dummy = ListNode(0)
    curr = dummy

    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next

    curr.next = l1 or l2
    return dummy.next


def list_to_linked(arr):
    """Helper: array to linked list."""
    dummy = ListNode(0)
    curr = dummy
    for val in arr:
        curr.next = ListNode(val)
        curr = curr.next
    return dummy.next


def linked_to_list(head):
    """Helper: linked list to array."""
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result


# Test
head = list_to_linked([4, 2, 1, 3])
sorted_head = merge_sort_linked_list(head)
print(linked_to_list(sorted_head))  # [1, 2, 3, 4]

---

8. Stability of Merge Sort

A sorting algorithm is stable if elements with equal keys maintain their relative order.

Merge sort is stable because in the merge step, when left[i] == right[j], we pick from left first (the <= in the comparison). This preserves the original relative order of equal elements.

def demonstrate_stability():
    """Show that merge sort is stable."""
    # Sort by first element, check that second elements maintain order
    data = [(3, 'a'), (1, 'b'), (3, 'c'), (2, 'd'), (1, 'e')]

    # Custom merge sort for tuples (sort by first element)
    def merge_sort_stable(arr):
        if len(arr) <= 1:
            return arr
        mid = len(arr) // 2
        left = merge_sort_stable(arr[:mid])
        right = merge_sort_stable(arr[mid:])

        result = []
        i = j = 0
        while i < len(left) and j < len(right):
            if left[i][0] <= right[j][0]:  # stable: <= picks left on tie
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        result.extend(left[i:])
        result.extend(right[j:])
        return result

    sorted_data = merge_sort_stable(data)
    print(sorted_data)
    # [(1, 'b'), (1, 'e'), (2, 'd'), (3, 'a'), (3, 'c')]
    # Notice: (1,'b') before (1,'e') and (3,'a') before (3,'c')
    # — original relative order preserved!


demonstrate_stability()

---

9. Time and Space Analysis

Time Complexity

At each level of recursion, we do O(n) total work (merging). There are log n levels (we halve the array each time). So total time is O(n log n).

This holds for all cases — best, average, and worst. Unlike quicksort, merge sort does not degrade on sorted or reverse-sorted input.

# Recurrence relation:
# T(n) = 2 * T(n/2) + O(n)
# By the Master Theorem: T(n) = O(n log n)

# Best case:  O(n log n)  — still splits and merges
# Average:    O(n log n)
# Worst case: O(n log n)  — guaranteed

Space Complexity

• Standard merge sort: O(n) auxiliary space for the merge buffer.
• Linked list merge sort: O(log n) for the recursion stack (merge is in-place for linked lists).
• Bottom-up merge sort: O(n) auxiliary space, but no recursion stack.

---

10. Merge Sort vs Other O(n log n) Sorts

Property	Merge Sort	Quick Sort	Heap Sort
Worst case	O(n log n)	O(n^2)	O(n log n)
Average case	O(n log n)	O(n log n)	O(n log n)
Space	O(n)	O(log n)	O(1)
Stable	Yes	No (typically)	No
Cache-friendly	Moderate	Yes	No
Linked lists	Excellent	Poor	Poor

When to choose merge sort:

• You need guaranteed O(n log n) worst case.
• You need a stable sort.
• You are sorting a linked list.
• You are doing external sorting (data too large for memory).

---

11. External Merge Sort

When data is too large to fit in memory, external merge sort divides the data into chunks that fit in memory, sorts each chunk, writes them to disk, and then merges the sorted chunks.

def external_merge_sort_concept(filename, memory_limit):
    """
    Conceptual outline of external merge sort.
    (Not a full implementation — shows the idea.)
    """
    # Phase 1: Create sorted runs
    # Read chunks that fit in memory, sort them, write to temp files
    runs = []
    chunk = []
    # ... read from filename in chunks of memory_limit ...
    # Sort each chunk with regular merge sort
    # Write sorted chunk to a temp file
    # Collect temp filenames in `runs`

    # Phase 2: K-way merge
    # Open all sorted run files
    # Use a min-heap to merge them
    import heapq

    # heap elements: (value, run_index)
    # Repeatedly pop the smallest, write to output, read next from that run
    # Continue until all runs are exhausted

    # This is how databases and tools like `sort` handle huge files
    pass

---

12. Natural Merge Sort

Natural merge sort takes advantage of existing sorted runs in the data, potentially reducing the number of merge passes.

def natural_merge_sort(arr):
    """
    Natural merge sort — finds existing sorted runs and merges them.

    Best case (already sorted): O(n)
    Worst case: O(n log n)
    """
    n = len(arr)
    if n <= 1:
        return arr[:]

    result = arr[:]

    while True:
        # Find all natural runs
        runs = []
        i = 0
        while i < n:
            start = i
            i += 1
            while i < n and result[i] >= result[i - 1]:
                i += 1
            runs.append((start, i))

        # If there's only one run, array is sorted
        if len(runs) == 1:
            break

        # Merge adjacent pairs of runs
        new_result = result[:]
        for k in range(0, len(runs) - 1, 2):
            lo1, hi1 = runs[k]
            lo2, hi2 = runs[k + 1]

            # Merge result[lo1:hi1] and result[lo2:hi2]
            merged = merge(result[lo1:hi1], result[lo2:hi2])
            new_result[lo1:hi2] = merged

        result = new_result

    return result


print(natural_merge_sort([1, 2, 3, 7, 4, 5, 6, 8]))
# Finds runs [1,2,3,7] and [4,5,6,8], merges once -> sorted

---

13. Practice Problems

Problem	Platform	Key Technique
Sort an Array (LC 912)	LeetCode	Basic merge sort
Sort List (LC 148)	LeetCode	Merge sort on linked list
Count of Smaller Numbers After Self (LC 315)	LeetCode	Modified merge sort
Reverse Pairs (LC 493)	LeetCode	Counting during merge
Count Inversions	GeeksforGeeks	Classic merge sort application
Merge k Sorted Lists (LC 23)	LeetCode	K-way merge
Sort Colors (LC 75)	LeetCode	Compare with merge sort
Merge Sorted Array (LC 88)	LeetCode	Core merge procedure

---

Big-O Summary

Operation	Time	Space
Merge sort (array)	O(n log n)	O(n)
Merge sort (linked list)	O(n log n)	O(log n)
Bottom-up merge sort	O(n log n)	O(n)
Count inversions	O(n log n)	O(n)
Merge two sorted arrays	O(n)	O(n)
Natural merge sort (best)	O(n)	O(n)

Merge sort is the algorithm you reach for when correctness and predictability matter more than raw speed. Its guaranteed O(n log n) and stability make it indispensable for real-world sorting — Python’s built-in sorted() uses Timsort, which is essentially a hybrid of merge sort and insertion sort.