[KMag]

Isn't that expected (within a constant factor of optimal depth, a.k.a. O(log N) tree height)? They're essentially building a treap, minus the in-order traversal of keys restriction.

[0] https://en.wikipedia.org/wiki/Treap

[eutectic]

Optimal depth for union-find is O(1); every node points directly to the root. It's a very different case than building a binary search tree.