Why O(n log n) Works

Each time an element is moved from one set to another, the new set is at least as large as the old one. So the set size at least doubles. Starting from size $1$, doubling $k$ times reaches size $2^k$. To reach $n$, you need $k = \log_2 n$ doublings.

An element cannot be moved more than $\log n$ times. Since there are $n$ elements total, and each moves at most $\log n$ times, total operations are $O(n \log n)$. This is the proof of the complexity bound.

Space complexity is $O(n)$ for the data structures used.