Is hedge union always as fast as divide and conquer?
While I have yet to see, or produce, a theoretical analysis of the hedge algorithms, I do have some empirical evidence that they are worse than the divide-and-conquer algorithms for binary trees.

Starting with the code in the Haskell containers package, I optimized the hedge union algorithm by manually applying call-pattern specialization to reduce intermediate allocation. This improved its performance by about 10%, giving it a fair shot.

Starting with the divide-and-conquer code in Adams, I optimized the union algorithm by adding special cases when either of the inputs is a singleton (the hedge union code optimizes one side thus, and it's not clear if the other side can be optimized similarly).

I tested each implementation using a collection of set operation benchmarks packaged with containers. Divide-and-conquer was usually faster than hedge, sometimes twice as fast. When it was slower, it was only slightly so.

Similar benchmarks of other set operations gave similar results.



Speculation:

Hedge algorithms may be helpful when using trees with a large branching factors, which may be more expensive to split recursively. They may also be helpful for small subtrees, where they may save enough allocation to be worth the extra work.