In the given solution above, union of two sets in case of treaps takes O(M.log(N/M)), whereas the merge operation would take O(M+N) which would be less compared to the one given.
M is always smaller than N. It will be O(N log^2 N) in the end.
Can u please elaborate on “O(N log^2 N)”.