Comment by 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.