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 into a set of size where , the result has size at least . The smaller set doubled in size. This doubling is the reason it works: every element can only be moved times before its set becomes too large. After doublings, the set reaches size and cannot grow further.