[sebastianmestre]

Please tell me that, after noticing that the best interval length is 2, you simplified your implementation to something like this

    def perform_union_dnc(paths):
        if len(paths) == 0:
            return None
        if len(paths) == 1:
            return paths[0]
        middle = len(paths) // 2
        left = perform_union_dnc(paths[:middle])
        right = perform_union_dnc(paths[middle:])
        return perform_union_naive([left, right])

It's not exactly the same algorithm (top-down merging instead of bottom-up) but the performance should be very close.

Also, it can be optimized to avoid temporary lists if that turns out to be a win.

[vg_head]

I didn't get to simplify the code further unfortunately. I could have, but I was running very tight on time with other things. In fact the running-in-production-version is even worse than what I've posted, I just went with what worked fast on the first try and moved on to something else immediately. But it can absolutely be improved further!