Pattern #26

Merge Sort

Important interview questions, thinking patterns, guaranteed O(N log N) sorting, 2-pointer merging, inversion counting, and Go rules.

Must Solve

12 core questions — solve these first.

1.Sort an Array
Standard Merge Sort O(N log N) guaranteed timemedium
2.Merge Two Sorted Lists
2-pointer linked list mergingeasy
3.Merge Sorted Array
In-place merge from right to left with 3 pointerseasy
4.Merge K Sorted Lists
Divide & conquer list pairs merge or Min-Heaphard
5.Count Inversions in an Array
Add (len(left) - i) when right[j] < left[i] during mergemedium
6.Reverse Pairs
Merge sort with condition nums[i] > 2*nums[j] during mergehard
7.Count of Smaller Numbers After Self
Merge sort with index array tracking right-side smaller elementshard
8.Sort List
Linked List Merge Sort using fast/slow pointers for middlemedium
9.Merge Intervals
Sort intervals by start time + single pass mergemedium
10.Median of Two Sorted Arrays
Binary Search partition across two sorted arrays (O(log(min(M,N))))hard
11.Maximum Subarray using Divide and Conquer
Split mid & calculate max left/right/cross sumsmedium
12.Merge Two Sorted Arrays Without Extra Space
Gap method (Shell Sort idea) or swap & sortmedium

Also Important

6 more questions worth practicing.

13.Smaller Numbers After Self
Index tracking merge sort inversion countinghard
14.Count Range Sum
Prefix sum array merge sort range counthard
15.Count of Range Sum
Prefix sum merge sort with range lower..upper checkhard
16.External Sorting Problems
Chunk sorting + K-way merge for data larger than RAMmedium
17.Sort Large Dataset / File
External Merge Sort disk chunkingmedium
18.Linked List Merge Sort
O(N log N) time & O(log N) stack space for linked listsmedium

How to Think

Need guaranteed efficient sorting?Merge Sort (O(N log N) worst case)
Can split array into halves?Split -> Sort Left -> Sort Right -> Merge
Already have two sorted arrays/lists?Two Pointers + Merge
Need count inversions / special pairs?Merge Sort + Count During Merge

Go Merge Sort Implementation

Complete Merge Sort & 2-Pointer Merge in Go

func mergeSort(nums []int) []int {
    if len(nums) <= 1 {
        return nums
    }

    mid := len(nums) / 2
    left := mergeSort(nums[:mid])
    right := mergeSort(nums[mid:])

    return merge(left, right)
}

func merge(a, b []int) []int {
    result := make([]int, 0, len(a)+len(b))
    i, j := 0, 0

    // Compare fronts and take smaller (use <= for stable sorting!)
    for i < len(a) && j < len(b) {
        if a[i] <= b[j] {
            result = append(result, a[i])
            i++
        } else {
            result = append(result, b[j])
            j++
        }
    }

    // Append remaining elements
    result = append(result, a[i:]...)
    result = append(result, b[j:]...)
    return result
}

👉 Guaranteed Time: O(N log N) | Extra Space: O(N)

Core Pattern & Lifecycle

1. SPLIT DOWN

Recursively split array in half until length <= 1 (single elements are already sorted!).

2. MERGE UP

Use two pointers i & j to merge two sorted arrays in O(N) time.

3. STABLE SORTING

When equal (a[i] == b[j]), pick from left array first (a[i] <= b[j]) to preserve original relative order.

Count Inversions Trick

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

During the merge step, if right[j] < left[i], since left is already sorted, right[j] is also smaller than ALL remaining elements in left!

// When right[j] < left[i] during merge:
inversions += len(left) - i

👉 Counts all split inversion pairs in O(N log N) time instead of brute force O(N²)!

Visual Memory Rule

Down = Split in half  |  Up = Merge two sorted halves with 2 pointers
Time  = O(N log N) guaranteed worst-case
Space = O(N) auxiliary memory
Stable = Use <= on comparison (take left first)

💡 Golden Rule: "Split until sorting is trivial, then merge the small sorted pieces back together."

Common Interview Mistakes

1. Wrong Base Case

Using len == 0 instead of len(nums) <= 1 causes infinite recursion.

2. Forgetting Remainder Slice

When one pointer finishes first, failing to append the remaining elements (a[i:] or b[j:]) drops data!

3. Using < Instead of <= for Stability

Using strict < takes from the right array on equality, destroying sort stability! Use <=.

4. Forgetting O(N) Space Complexity

Merge Sort is O(N log N) time, but requires O(N) extra array memory. Always mention both in interviews!

Interview Rules

1. Guaranteed O(N log N) sorting? → Merge Sort
2. Split in halves? → mid := len(nums) / 2
3. Merge sorted arrays/lists? → Two Pointers (O(N) merge)
4. Count inversions / reverse pairs? → Count during Merge step
5. Linked List sorting? → Merge Sort using Fast/Slow pointers for middle
6. Large file sorting (> RAM)? → External Merge Sort
7. Stable sort needed? → Merge Sort is stable when taking left first on equality (<=)
8. Overall Complexity → O(N log N) time, O(N) space

Small Rules

Rule 1:Base case is len(nums) <= 1 (single elements are already sorted).
Rule 2: Split array at mid := len(nums) / 2.
Rule 3: The merge step requires both left and right sub-arrays to be sorted.
Rule 4: Merging two sorted arrays of total size N takes O(N) time with two pointers.
Rule 5: Merge Sort time remains strictly O(N log N) even in the worst case scenario.

Production Thinking

External Large File Sorting → Sort 100GB log files by loading 1GB RAM chunks, sorting, and merging chunks from disk

Merging Timestamped Server Logs → Combine already sorted log streams from Server A & Server B in O(N) time

Database Storage Engines → LSM-Trees (RocksDB, Cassandra) use SSTable merge-sort runs during compaction

Distributed Data Aggregation → Sort chunk partitions on worker nodes, then merge results at master node

Remember This

Merge Sort            → Split + Merge
Base case             → 1 element
Split                 → Half + Half
Merge                 → Two Pointers
Time                  → O(n log n)
Space                 → O(n)
Stable                → Yes, if merged carefully
Linked List           → Great fit
Huge files            → External Merge Sort

💡 Golden Rule: "Split until sorting is trivial, then merge the small sorted pieces back together."