Skip to content

Merge Sort & Running Pointers: A Divide & Conquer Approach

1. Prerequisites & Mathematical Foundation

Before diving into the algorithm, we must establish the mathematical properties that define its complexity and structure.

  • Geometric Series of Complexity: When we sum the work done at each level of a divide and conquer algorithm (\(N + N/2 + N/4 + \dots\)), we are essentially calculating a geometric series.

    • Formula: \(1 + 2 + 2^2 + \dots + 2^h = 2^{h+1} - 1\).
    • Binary Analogy: Consider 5 bits: \(11111_2\). If you add \(1\), you get \(100000_2\) (\(2^5\)). Thus, \(\sum_{i=0}^{4} 2^i = 2^5 - 1\).
    • Implication: This is why the total nodes in a perfect binary tree are \(\approx 2 \times \text{Leaves}\). In complexity terms, \(O(N) + O(N/2) + \dots = O(2N) \approx O(N)\).

  • Merge Two Sorted Lists: The core operation is merging two already sorted arrays.

    • Given Array A (size \(N\)) and Array B (size \(M\)).
    • We can merge them in \(O(N + M)\) time using two pointers.

2. Structural Analysis: The Binary Tree

To understand the space and recursion depth, we model the array as a Binary Tree.

  • Tree Types:

    • Full Binary Tree: Every node has either 0 or 2 children.
    • Complete Binary Tree: Filled level by level, left to right.
      • Nodes at height \(h\): Range \((2^{h-1}, 2^h]\).
    • Perfect Binary Tree: All levels completely filled. Total nodes = \(2^{h+1} - 1\).

  • Height & Balance:

    • If total nodes \(N \approx 2^h\), then \(h \approx \log_2 N\). This guarantees the recursion depth is logarithmic.

  • Array as a Tree (Space Analysis): We can represent an array of size \(N\) (where \(N=2^h\)) as the leaves of a tree.

    • Root: Represents range \([0, 2^h)\).
    • Left Child: \([0, 2^{h-1})\).
    • Right Child: \([2^{h-1}, 2^h)\).
    • Space Requirement: To build a tree on top of an array of size \(N\), we need an array of size \(2N\) (specifically \(2^{h+1} - 1\)).

3. The Core Concept: Why Sort?

Why do we go through the trouble of sorting? Sorted data is the best kind of data. Inequalities become predictable (monotonic) when data is sorted.

Examples of simplification via sorting:

  1. Inversions (\(arr[i] > arr[j]\)): In a sorted array, this is always 0.
  2. Equality pairs (\(arr[i] == arr[j]\)): In a sorted array, identical elements are adjacent. We can just count the frequency \(k\) of each number and do \(^kC_2\) (combinations).
    • Example: [1, 2, 2, 2, 3, 3, 3, 3] \(\to\) \(1C_2 + 3C_2 + 4C_2\).
  3. Reverse Pairs (\(arr[i] > 2 \cdot arr[j]\)): In a sorted array (ascending), this is 0.
  4. Diff Pairs (\(abs(arr[i] - arr[j]) = k\)): Becomes \(arr[i] = arr[j] - k\). We can just use a unordered_map to store previous counts or binary search.
  5. Half Pairs (\(arr[i] < arr[j] / 2\)): This simplifies to easy pointer movement because increasing \(arr[j]\) creates more "space" for the condition to hold.

The "Space" Intuition: When we have an inequality like \(arr[i] < arr[j]/2\): If we increment \(j\) (increasing \(arr[j]\)), we create "more space" for \(arr[i]\) to satisfy the condition. This allows \(i\) to move forward without resetting, giving us linear \(O(N)\) logic.

Math Analogy: If \(a < b\), then clearly \(a+x < b+x\) for any positive \(x\). As the right side grows, the "ceiling" for the left side lifts, allowing us to include more elements.

4. The Algorithm: Running Pointers on Merge Sort

We utilize the structure of Merge Sort. At any node in the recursion, we have a Left child and a Right child.

  • Crucial Property: Before we merge them, Left is sorted and Right is sorted.
  • Index Property: Every element in Left has a smaller original index than every element in Right.

The Flow:

  1. sort(left)
  2. sort(right)
  3. The "Hook": count += calculate_pairs(left, right)
  4. Here, \(i\) scans Left, \(j\) scans Right.
  5. We know \(i < j\) (by index). We just check the value constraint.
  6. merge(left, right)

5. Detailed Dry Run

Input Array: [3, -1, 7, 10, -3, 0, 2, 6] We want to sort this and count pairs satisfying a constraint (e.g., \(arr[i] > arr[j]\)).

Step 1: Leaf Level Merges

  • [3] and [-1] merge \(\to\) [-1, 3]
  • (Check constraint here: \(3 > -1\)? Yes. Count it.)
  • [7] and [10] merge \(\to\) [7, 10]
  • [-3] and [0] merge \(\to\) [-3, 0]
  • [2] and [6] merge \(\to\) [2, 6]

Step 2: Intermediate Merges

  • Merge [-1, 3] and [7, 10]
  • Left: [-1, 3], Right: [7, 10]
  • Running Pointers: Compare elements in Left vs Right.
  • Merged Result: [-1, 3, 7, 10]
  • Merge [-3, 0] and [2, 6]
  • Left: [-3, 0], Right: [2, 6]
  • Merged Result: [-3, 0, 2, 6]

Step 3: Final Merge

  • Merge [-1, 3, 7, 10] and [-3, 0, 2, 6]
  • Left: [-1, 3, 7, 10]
  • Right: [-3, 0, 2, 6]
  • Calculation Hook: Fix \(j\) in Right, move \(i\) in Left (or vice versa) to count valid pairs.
  • Final Merged Array: [-3, -1, 0, 2, 3, 6, 7, 10]

6. Pivot Separation & Proof

Question: How do we ensure we count every pair exactly once? The "Pivot" Proof: For any pair \((i, j)\) where \(i < j\), there is a unique level in the recursion tree where:

  1. \(i\) ends up in the Left child's range.
  2. \(j\) ends up in the Right child's range.
  3. Before this level, they were isolated. After this level, they are mixed. Example: At the leaf level, the split separates indices \(id-1\) and \(id\). This partition ensures exhaustive coverage without duplication.

7. Implementation: Generic C++ Code

This template supports any inequality by changing the lambda function.

### C++ Generic Implementation (Click to expand) 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Recursive solver using templates for generic predicates
template <typename Func>
long long solve(vector<long long>& arr, int l, int r, Func pred) {
    if (l >= r) return 0;

    int mid = l + (r - l) / 2;
    long long count = solve(arr, l, mid, pred) + solve(arr, mid + 1, r, pred);

    // Pass 1: Count valid pairs using two pointers
    // Strategy: Forward-Forward 
    // We iterate i (Left) and move j (Right) to find the valid prefix.
    int j = mid + 1;
    for (int i = l; i <= mid; ++i) {
        // While the condition is met, extend the range [mid+1...j]
        while (j <= r && pred(arr[i], arr[j])) {
            j++;
        }
        count += (j - (mid + 1));
    }

    // Pass 2: Sort using standard library (In-place merge)
    inplace_merge(arr.begin() + l, arr.begin() + mid + 1, arr.begin() + r + 1);

    return count;
}

template <typename Func>
long long count_pairs(vector<long long> arr, Func pred) {
    return solve(arr, 0, (int)arr.size() - 1, pred);
}

int main() {
    vector<long long> data = {3, -1, 7, 10, -3, 0, 2, 6}; // Data from Dry Run

    // Example: Count Inversions (Left > Right)
    cout << "Inversions: " << count_pairs(data, [](long long a, long long b) { 
        return a > b; 
    }) << "\n";

    // Example: Reverse Pairs (Left > 2 * Right)
    cout << "Reverse Pairs: " << count_pairs(data, [](long long a, long long b) { 
        return a > 2 * b; 
    }) << "\n";

    return 0;
}

8. Practice Resources