Merge method

When a graph algorithm discovers a connection between two elements, it may need to record that they now belong to the same group. A disjoint set does this with `merge(x, y)`: it combines the partitions containing `x` and `y`. The client defines what the connection means; the data structure tracks the resulting groups. section 5.3 section 5.8

First find each element’s partition. If both results identify the same partition, return `false`: nothing needs to change. Otherwise, combine the partitions and return `true`. Calling `findPartition` also validates the inputs in the implementations shown here. section 5.4.1 section 5.5.2

The cost depends on how a partition is represented:

• With a map from elements to sets, move every element of one set into the other and update its map entry. This takes linear time in the worst case. Choosing the smaller set to move reduces the number of updates, but does not make a single merge constant-time. section 5.4.1
• With parent-linked trees, find both roots, then make one root point to the other. No elements need to be moved individually; the cost now depends on finding the roots, which can require a walk proportional to tree height. section 5.5.2
• For better performance, attach the smaller tree beneath the larger one and update the larger root’s stored size, called `rank` in this implementation. Path compression happens during `findPartition`, not during merge. section 5.6.2 section 5.6.2

function merge(elem1, elem2)               #1
  r1 ← this.findPartition(elem1)           #2
  r2 ← this.findPartition(elem2)           #2
  if r1 == r2 then                         #3
    return false
  info1 ← this.parentsMap[r1]              #4
  info2 ← this.parentsMap[r2]
  if info1.rank >= info2.rank then         #5
    info2.root ← info1.root;               #6
    info1.rank += info2.rank;              #7
  else
    info1.root ← info2.root;               #6
    info2.rank += info1.rank;              #7
 return true

The tree-with-heuristics pseudocode shows the complete decision: find both roots, reject an already-merged pair, then attach the smaller tree and update the surviving root’s rank. section 5.6.2

The simple map-and-set version is straightforward when linear-time merges are acceptable. Tree representation removes the need to rewrite a whole partition; balancing and path compression improve it further. The optimized merge operation’s running time is described in terms of the inverse Ackermann function. section 5.4.1 section 5.5.2 section 5.8