Plain Union-Find only ever merges parent pointers —
"same set?" and "join these two sets" cost next to nothing because there's nothing to move but a single
pointer. Real uses often attach something heavier to each set: a list of members, a running count, a set
of distinct colors seen so far. Every union then has to merge that attached data too, and how it
merges is no longer free. Copy the second set's data into the first's every time, without checking which
side is bigger, and a single adversarial sequence of unions can cost O(n²) in total —
building up one big set element by element while always copying that whole growing set into whatever tiny
newcomer just joined. Small-to-large merging is one rule that fixes it: always copy the
smaller set's data into the larger, never the reverse. That one size comparison per union is
enough to guarantee every element moves at most O(log n) times in total, no matter what order
the unions arrive in — because a move only ever happens as part of landing in a set at least as big as the
mover's own, so each move at least doubles the size of whatever set the mover ends up in, and a quantity
that keeps doubling can only do so log₂ n times before it reaches n.
Like Offline Lowest Common Ancestor,
this is the site's sixth Disjoint Set entry and the second one that isn't a variant of find/
union themselves — it's a rule for merging whatever data rides along with each set, layered on
top of plain union-find bookkeeping. It's the standard trick behind "DSU on tree" (merging each subtree's
attached set into its parent's, bottom-up, to answer questions like "how many distinct values appear in
this subtree" without re-scanning anything) and behind any offline algorithm that keeps a growing container
per component and needs the total merge cost, across every union it ever performs, to stay well below
quadratic.
Eight elements, each starting as its own singleton holding just itself. Pick a sequence —
chain merges one growing set with a new singleton each step; balanced pairs merges
same-size groups in a binary tournament — and a merge rule — naive always copies
the second argument's set into the first's, regardless of size; small-to-large always copies
whichever side is smaller. Press Step or Run to walk the fixed sequence
of seven unions: the elements that physically move this step light up tan, the root they land in turns
solid, and the counters below track how many elements moved this step and in total. Switch the merge rule
without changing the sequence to see the same seven unions cost 7 total moves one way and
28 the other — nothing about which sets end up together changes, only how expensive
getting them there was.
The doubling argument. Whenever an element moves, it's because it belonged to the
smaller (or tied) side of a union — so the set it lands in has size at least double what its own set was
the instant before the move. A single element's size-of-current-set can double at most log₂ n
times before exceeding n, so that element can move at most log₂ n times, ever,
across the entire sequence of unions — not just the two shown in the demo, any sequence. Summed
over all n elements, total moves across the whole run are bounded by
O(n log n). Nothing about this argument depends on the order unions arrive in or which
elements happen to be involved; it only depends on the one rule being followed every single time.
Measured, not just argued. The two sequences in the demo above make the gap concrete:
| sequence | n | naive total moves | small-to-large total moves |
|---|---|---|---|
| chain | 8 | 28 | 7 |
| balanced pairs | 8 | 12 | 12 |
| chain | 64 | 2,016 | 63 |
| balanced pairs | 64 | 192 | 192 |
Chain's naive total is exactly n(n − 1)/2 — the classic triangular-number blowup, one
worse step than the last, because the naive rule keeps copying the entire growing accumulator into each
tiny newcomer instead of the other way around. Small-to-large's chain total is exactly n − 1:
one move per union, the cheapest any correct merge could possibly be, since the smaller side is always the
single newest element. Balanced pairs is the more interesting row: every merge there combines two
equal-sized groups, so there's no smaller side to exploit — naive and small-to-large move exactly
the same (n log₂ n)/2 elements either way (12 at n = 8,
192 at n = 64), which is itself an instance of the O(n log n) bound,
just reached by both strategies at once instead of only guaranteed for one. The lesson isn't "naive is
always bad" — it's that naive has no ceiling on how bad an imbalanced sequence can get, where
small-to-large always does.
A third check, not shown in the demo (n = 8 and 64 are small enough to reason about by hand; the bound's
claim is about every sequence, not just two hand-picked ones): 2,000 random union sequences over
n = 300 elements, replayed once under each rule. Small-to-large's total moves never once
exceeded the n log₂ n = 2,469 bound across all 2,000 runs — the worst observed run moved
2.15 elements per element on average, nowhere near even the log₂ 300 ≈ 8.23
theoretical ceiling. Naive, replayed on the exact same random sequences, had no such luck: its worst run
moved 62.43 elements per element on average — not a modest slowdown, a nearly 30× wider margin
than small-to-large's worst case on the identical input.
Matches the demo above: each root carries a plain array of whatever the attached data is (here, just
the element ids that ended up in that set), and union compares sizes before deciding which
array gets copied into which.
class SmallToLargeDSU {
#parent;
#data; // #data[r] is the attached array for root r; meaningless once r stops being a root
#moves = 0;
constructor(n) {
this.#parent = Array.from({ length: n }, (_, i) => i);
this.#data = Array.from({ length: n }, (_, i) => [i]);
}
find(x) {
while (this.#parent[x] !== x) x = this.#parent[x];
return x;
}
totalMoves() { return this.#moves; }
// merges the sets containing a and b; returns the number of elements that
// physically moved this call (0 if a and b were already in the same set)
union(a, b) {
let ra = this.find(a), rb = this.find(b);
if (ra === rb) return 0;
// the only line that distinguishes this from the naive "always merge b into a" rule
if (this.#data[ra].length < this.#data[rb].length) [ra, rb] = [rb, ra];
const moved = this.#data[rb].length;
this.#data[ra].push(...this.#data[rb]);
this.#data[rb] = []; // rb is no longer a root — its array is never read again
this.#parent[rb] = ra;
this.#moves += moved;
return moved;
}
}The size check is the entire technique — drop it and correctness survives but the guarantee
vanishes silently. Delete the one if line above (always merge rb into
ra, the plain "naive" rule from the demo) and every method still returns the right answer for
every query; nothing crashes, nothing looks wrong in a quick test. The only symptom is total move count on
an unlucky sequence — exactly the gap the chain row of the table above measures. That makes it a dangerous
class of bug: it can ship, pass tests, and only show up as "why is this so slow" on whatever real input
happens to be size-imbalanced, with no error message pointing back at the missing check.
The bound is about the whole sequence, not any single union. A single small-to-large
union can still move up to n/2 elements (merging two equal, maximal halves) — same as naive,
same as any correct merge. What small-to-large actually promises is that expensive unions like that one are
rare enough, and each element's own share of them small enough, that the sum across every union in the
sequence stays O(n log n). Don't read "amortized" here as "cheap every time" — the balanced
row above has every single union costing exactly half the elements in play, and that's still fine.
This bounds merge cost, not find cost. Nothing here touches path
compression or union by rank — the find loop above is the plain, uncompressed walk, and nine
unions on eight elements never makes that a problem in the demo. On a larger structure it would be exactly
the same gap Union-Find's own Pitfalls section
describes: skip both of those optimizations and find degrades toward
O(n), regardless of how well the attached data merges. The two techniques solve different
problems and are meant to be used together, not as substitutes for each other.
Time: O(n log n) total, amortized across an entire sequence of unions on
n elements — not a per-operation bound. Any individual union costs O(1) extra
for the size comparison itself, plus however many elements its smaller side happens to hold, which can
range from 0 (already in the same set) up to n/2. Space:
O(n) total across every root's attached array combined — the same n elements are
just redistributed among fewer, larger arrays as unions proceed, never duplicated.
This site's guide, Choosing a Union-Find
Variant, places this entry among the applications built on top of Union-Find rather than the
four core variants it actually compares — it answers a different question again from the other
applications: not "how do I merge sets faster," but how to merge whatever data is attached to each
set without that blowing up past O(n log n) total.