For this problem I am not sure I understand why the complexity is good for the official solution. I get small to large merging in general why it is N log N, but the merge function only merges rpar from small to large, and I don’t think it guarantees that adj is merged from small to large? Which I would think would be very bad for complexity. So, could someone explain why the complexity does not suffer from this? Thanks
This ensures that no element of rpar is moved more than \log_2N times (same reasoning for elements of adj).