The Core idea

What if you always merge the smaller set into the larger one?

Instead of arbitrary order, choose the merge direction wisely. When you merge a set of size $s$ into a set of size $t$ where $s \leq t$, the result has size at least $2s$. The smaller set doubled in size. This doubling is the reason it works: every element can only be moved $O(\log n)$ times before its set becomes too large. After $\log n$ doublings, the set reaches size $n$ and cannot grow further.