解説 PDF では、weighted-union heuristic により時間計算量が \(O(N\log N)\) であると記述されています（理由説明なし）。 実際には、線形時間 \(\Theta(N)\) で動くので、指摘しておきます。\(\Theta(N\log N)\) が主張されているわけではないので誤りではないですが。

\(1\) 元からなるデータを \(N-1\) 回マージして、\(N\) 元のデータを作ります。

• 大きさ \(n\), \(m\) のデータを \(O(\min(n,m))\) 時間かけて、大きさ \(n+m\) のデータへとマージする場合：\(O(N\log N)\) 時間。
• 大きさ \(n\), \(m\) のデータを \(O(\min(n,m))\) 時間かけて、大きさ \(\max(n,m) + O(1)\) のデータへとマージする場合：\(O(N)\) 時間。

で、今回は、後者のパターンです。

前者の場合、ひとつひとつの要素が移動する回数を数えて \(O(N\log N)\) という計算量解析をしますが、後者の場合、ひとつの要素の移動（というより削除と見なすと良い？）は \(1\) 回ずつです。