Minimum number of tree operations to normalize a labeled tree
$O(n \log n)$ operations suffice, as you conjectured.  One can implement something akin to quicksort (using the median as the pivot in each stage).  I'll describe the details below.  For simplicity of exposition, let's assume $n$ is a power of two (though it all works for arbitrary powers of two).  We'll bring the tree into a normal form, which is a complete binary tree (i.e., all leaves are at the same depth, $\lg n$).

Let $\alpha$ be the $n/2$th label (in sorted order of the labels).  We'll first manipulate the tree so it has the form $xy$, where $x$ is a subtree of size $n/2$ containing all items $\le \alpha$ and $y$ is a subtree of size $n/2$ containing all items $&gt;\alpha$.  Call this the partition operation.  Then, we'll recursively apply the algorithm to the left subtree and to the right subtree.

I'll argue below that the partition operation can be done with $O(n)$ operations.  Then it follows that the total number of operations performed by this algorithm obeys the recurrence relation

$$T(n) = 2 T(n/2) + O(n),$$

which has the solution $T(n) = O(n \log n)$. It follows that this algorithm takes $O(n \log n)$ operations.

So how do we do the partition operation?  Well, suppose the tree is originally of the form $uv$.  We'll recursively apply the partition algorithm to $u$, to get a tree of the form $u_0u_1$ where the leaves of $u_0u_1$ are the same as the leaves of $u$, but now $u_0$ has all items of $u$ that are $\le \alpha$ and $u_1$ has the items that are $&gt;\alpha$.  Similarly, we'll recursively apply the partition algorithm to $v$, to get $v_0v_1$.  So after the recursive calls to the partition algorithm, the tree has the form $(u_0u_1)(v_0v_1)$.  Now by a constant number of applications of commutatively and associativity, this can be transformed to $(u_0v_0)(u_1v_1)$.  At this point, the tree has the desired form, as $u_0v_0$ is composed of all of the items of $uv$ that are $\le \alpha$ and $u_1v_1$ is composed of all of the items of $uv$ that are $&gt;\alpha$.

The running time of the partition algorithm is given by the recurrence

$$U(n) = 2U(n/2) + O(1),$$

which has the solution $U(n) = O(n)$.  Thus, the partition algorithm can be done in $O(n)$ operations.