Adams describes a divide-and-conquer algorithm for finding the union of two sets (represented as weight-balanced binary search trees). He then describes a then-new "hedge union" algorithm which he claims improves on the divide-and-conquer one. However, he does not offer a proof, or even a real explanation, of why it should be $O(m + n)$, let alone why it should be faster than divide-and-conquer.
Blelloch, Ferizovic, and Sun show that Adams's divide-and-conquer algorithm actually attains the theoretically optimal $\Theta (m \log (n/m + 1))$ where $m \le n$. They do not, however, address the hedge union algorithm.
Is hedge union, in fact, as efficient as divide-and-conquer? The least obvious part is the inner trim. It appears, at least superficially, to duplicate work between the left and right subtrees that the full split shares between them. Perhaps this is okay for some reason, but I don't know why.
A further inquiry: Haskell's Data.Set
and Data.Map
use hedge variants of intersection and difference, as well as union. I have not found any published discussion of those algorithms at all. Similar questions apply to these as well.