Does it actually get called n-1 times. It seems like it would be called fewer since it's not called on leaves. I'm not sure if there's an exact way to express it. Perhaps we should just use big O.

A full binary tree with n leaves (our case) has always n-1 internal nodes (2n-1 nodes in total). And since merge gets called for each internal node we have n-1 merge operations.