Small-to-Large Merging (non-graph uses)

Why Small-to-Large Merging (non-graph uses) Matters

When solving problems that involve combining sets, frequency maps, or priority queues across hierarchical subproblems—such as divide-and-conquer range partitions, segment tree node merges, suffix automata state combinations, or disjoint set aggregations—a naive merge copies all elements from one container to another. If an algorithm blindly merges a larger collection into a smaller collection, or merges containers in an arbitrary order, a single element can be copied up to $O(N)$ times, driving the total time complexity to $O(N^2)$.

Small-to-Large Merging (also known as the weighted-merge heuristic) solves this performance bottleneck through a simple invariant: whenever two collections $A$ and $B$ must be merged, always identify the smaller container, swap container references in $O(1)$ time if necessary so that $B$ is the larger container, and then iterate through the elements of $A$ to insert them into $B$. Because the destination container is guaranteed to be at least as large as the source container, the size of the set containing any given element at least doubles every time that element is migrated. Consequently, no individual element can be moved more than $\lfloor \log_2 N \rfloor$ times across all merge operations, reducing the total runtime bound from $O(N^2)$ to $O(N \log N)$ or $O(N \log^2 N)$.

Core Concepts and Terminology

In non-graph settings, Small-to-Large Merging applies to any data structure where two independent dynamic collections (such as std::set, std::map, unordered_set, or priority queues) need to be combined into a single unified collection representing the union or aggregate state of subproblems.

The key components of the algorithm are:

1. Source (Smaller) Collection ($A$): The container holding fewer elements. Its elements are iterated over and transferred one by one.
2. Destination (Larger) Collection ($B$): The container holding more elements. It absorbs all elements from $A$.
3. Reference / Pointer Swap: An $O(1)$ operation that swaps the memory addresses or container handles of $A$ and $B$ whenever $ A| > |B|$, ensuring $B$ is always the larger destination.
4. Size-Doubling Invariant: The mathematical principle that if an element $x$ in a set of size $|A|$ is merged into a set $B$ with $|B| \ge |A|$, the resulting set has size $|A \cup B| \ge 2 |A|$.

How Small-to-Large Merging (non-graph uses) Works, Step by Step

The control flow for Small-to-Large Merging follows a strict sequence to ensure optimal time complexity:

1. Size Comparison: Given two containers $A$ and $B$, evaluate their sizes $\vert{}A\vert{}$ and $\vert{}B\vert{}$.
2. Conditional Pointer Swap: If $\vert{}A\vert{} > \vert{}B\vert{}$, execute an $O(1)$ reference swap swap(A, B). After this step, $B$ is guaranteed to be the larger container, and $A$ is the smaller container.
3. Element Migration Loop: Iterate through every element $x \in A$. Insert $x$ into $B$, updating any associated frequency counts or aggregate statistics.
4. Container Disposal / Reset: Clear $A$ or allow it to be garbage collected. Return $B$ as the representative merged container.

The control flow diagram below summarizes the decision-making and loop structure:

flowchart TD
A[Start: merge_containers container_A, container_B] --> B{len container_A > len container_B?}
B -- Yes --> C[Swap pointers/references: swap container_A, container_B]
B -- No --> D[Keep container_B as destination]
C --> D
D --> E[For each element x in container_A]
E --> F[Insert x into container_B & update statistics]
F --> G{More elements in container_A?}
G -- Yes --> E
G -- No --> H[Clear container_A]
H --> I[Return container_B]

Worked Example with a Full Trace

Consider a divide-and-conquer problem where four initial subsets of element IDs must be combined pairwise across two merge stages:

• Initial Subsets:
• $S_0 = \{10, 20\}$ (size 2)
• $S_1 = \{30\}$ (size 1)
• $S_2 = \{20, 40, 50\}$ (size 3)
• $S_3 = \{10, 50, 60, 70\}$ (size 4)

• Merge Operations: 1. merge(S_0, S_1): Compare size $2$ vs $1$. $S_0$ is larger, so $S_1$ migrates into $S_0$. Result: $S_0 = \{10, 20, 30\}$ (size 3). Total element moves: 1. 2. merge(S_0, S_2): Compare size $3$ vs $3$. Sizes are equal, so no swap needed. $S_2$ migrates into $S_0$. Result: $S_0 = \{10, 20, 30, 40, 50\}$ (size 5). Total element moves: $1 + 3 = 4$. 3. merge(S_3, S_0): Compare size $4$ vs $5$. $S_3$ (size 4) is smaller than $S_0$ (size 5), so references swap swap(S_3, S_0). $S_3$'s 4 elements migrate into $S_0$. Result: $S_0 = \{10, 20, 30, 40, 50, 60, 70\}$ (size 7). Total element moves: $4 + 4 = 8$.

Notice that without Small-to-Large Merging, blindly merging $S_0$ (size 5) into $S_3$ (size 4) would have moved 5 elements instead of 4.

Implementation in Python, C++, and Java

The complete code implementations below showcase Small-to-Large Merging on non-graph data structures. All three programs implement identical logic, process the exact same sequence of set merges, and produce identical terminal output.

def solve_small_to_large():
    # Initial sets
    sets = [
        {10, 20},            # Set 0 (size 2)
        {30},                # Set 1 (size 1)
        {20, 40, 50},        # Set 2 (size 3)
        {10, 50, 60, 70}     # Set 3 (size 4)
    ]

    merges = [(0, 1), (0, 2), (3, 0)]

    for step, (id_a, id_b) in enumerate(merges, 1):
        s_a = sets[id_a]
        s_b = sets[id_b]

        size_a_before = len(s_a)
        size_b_before = len(s_b)

        # Small-to-large check: guarantee s_a is large, s_b is small
        swapped = False
        if len(s_a) < len(s_b):
            s_a, s_b = s_b, s_a
            swapped = True

        # Migrate elements from smaller set (s_b) into larger set (s_a)
        for elem in s_b:
            s_a.add(elem)

        # Update reference in global list
        sets[id_a] = s_a
        sets[id_b] = set()  # Clear small set

        print(f"Merge {step}: Small size {min(size_a_before, size_b_before)} -> "
              f"Large size {max(size_a_before, size_b_before)} | "
              f"Swapped: {swapped} | Result size: {len(s_a)}")


if __name__ == "__main__":
    solve_small_to_large()

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

void solve_small_to_large() {
    std::vector<std::set<int>> sets = {
        {10, 20},            // Set 0 (size 2)
        {30},                // Set 1 (size 1)
        {20, 40, 50},        // Set 2 (size 3)
        {10, 50, 60, 70}     // Set 3 (size 4)
    };

    std::vector<std::pair<int, int>> merges = {{0, 1}, {0, 2}, {3, 0}};

    for (size_t step = 0; step < merges.size(); ++step) {
        int id_a = merges[step].first;
        int id_b = merges[step].second;

        int size_a_before = static_cast<int>(sets[id_a].size());
        int size_b_before = static_cast<int>(sets[id_b].size());

        bool swapped = false;
        if (sets[id_a].size() < sets[id_b].size()) {
            std::swap(sets[id_a], sets[id_b]);
            swapped = true;
        }

        // Migrate elements from sets[id_b] (smaller) into sets[id_a] (larger)
        for (int elem : sets[id_b]) {
            sets[id_a].insert(elem);
        }

        sets[id_b].clear();

        int small_size = std::min(size_a_before, size_b_before);
        int large_size = std::max(size_a_before, size_b_before);

        std::cout << "Merge " << (step + 1) << ": Small size " << small_size
                  << " -> Large size " << large_size
                  << " | Swapped: " << (swapped ? "True" : "False")
                  << " | Result size: " << sets[id_a].size() << "\n";
    }
}

int main() {
    solve_small_to_large();
    return 0;
}

import java.util.*;

public class Main {
    public static void solveSmallToLarge() {
        List<Set<Integer>> sets = new ArrayList<>();

        sets.add(new TreeSet<>(Arrays.asList(10, 20)));          // Set 0 (size 2)
        sets.add(new TreeSet<>(Collections.singletonList(30)));  // Set 1 (size 1)
        sets.add(new TreeSet<>(Arrays.asList(20, 40, 50)));      // Set 2 (size 3)
        sets.add(new TreeSet<>(Arrays.asList(10, 50, 60, 70))); // Set 3 (size 4)

        int[][] merges = {{0, 1}, {0, 2}, {3, 0}};

        for (int step = 0; step < merges.length; step++) {
            int idA = merges[step][0];
            int idB = merges[step][1];

            int sizeABefore = sets.get(idA).size();
            int sizeBBefore = sets.get(idB).size();

            boolean swapped = false;
            if (sets.get(idA).size() < sets.get(idB).size()) {
                Set<Integer> temp = sets.get(idA);
                sets.set(idA, sets.get(idB));
                sets.set(idB, temp);
                swapped = true;
            }

            // Migrate elements from smaller set (idB) into larger set (idA)
            for (int elem : sets.get(idB)) {
                sets.get(idA).add(elem);
            }

            sets.get(idB).clear();

            int smallSize = Math.min(sizeABefore, sizeBBefore);
            int largeSize = Math.max(sizeABefore, sizeBBefore);

            System.out.println("Merge " + (step + 1) + ": Small size " + smallSize
                    + " -> Large size " + largeSize
                    + " | Swapped: " + (swapped ? "True" : "False")
                    + " | Result size: " + sets.get(idA).size());
        }
    }

    public static void main(String[] args) {
        solveSmallToLarge();
    }
}

Complexity, Correctness, and Invariants

The runtime analysis of Small-to-Large Merging relies on analyzing the total work performed on an individual element rather than analyzing each container merge operation in isolation.

Consider an element $x$ originally residing in a collection of size $1$. Each time $x$ is migrated during a merge step, it is moved from a smaller collection $A$ into a collection $B$ where $\vert{}B\vert{} \ge \vert{}A\vert{}$. The combined collection $A \cup B$ has a size of at least $\vert{}A\vert{} + \vert{}B\vert{} \ge 2 \vert{}A\vert{}$. Because the size of $x$'s enclosing collection at least doubles with every migration, and the maximum possible size of any collection is $N$ (the total number of elements across all initial sets), $x$ can be migrated at most $\lfloor \log_2 N \rfloor$ times.

Across all $N$ elements, the total number of element insertions is bounded by $O(N \log N)$. Depending on the underlying container used:

• Balanced Search Tree (std::set / TreeSet): $O(\log N)$ per insertion $\implies$ Total time $O(N \log^2 N)$.
• Hash Table (unordered_set / HashSet): $O(1)$ amortized per insertion $\implies$ Total time $O(N \log N)$.

Variants, Pitfalls, and Optimizations

Small-to-Large Merging extends beyond simple sets to various non-graph dynamic structures:

1. Segment Tree Merging / Trie Merging:

When combining segment trees or tries in non-graph settings (e.g., merging interval frequency distributions or string prefix counts), nodes are merged recursively. If one child subtree is empty, the non-empty pointer is returned directly in $O(1)$ time. 2. Priority Queue / Heap Merging: Merging two binary heaps naively takes $O(\vert{}A\vert{} \log(\vert{}A\vert{} + \vert{}B\vert{}))$. Using Small-to-Large Merging by popping elements from the smaller heap and pushing into the larger heap guarantees $O(N \log^2 N)$ total time across all merges, without needing meldable heap algorithms (like Skew or Leftist heaps). 3. Frequency Map Merging with Offset Tags: When tracking element counts with range shifts ($f(x + c)$), maintain a lazy offset tag on each map. Swapping map references swaps their offset tags in $O(1)$ time.

Practice Problems and Real-World Use

Small-to-Large Merging is applied across various non-graph algorithmic structures and production software systems: