Given a binary tree with labels on the leaves, like $(bc)(ad)$ or $((af)e)(c(db))$, which we can interpret as a product of terms with respect to a commutative associative operation, how many applications of commutativity (swapping the two children of a node) and associativity (tree rotations) are needed to bring this tree to a sorted normal form like $a(b(cd))$ or $a(b(c(d(ef))))$? Examples:
$$(bc)(ad)\mapsto((bc)a)d\mapsto(a(bc))d\mapsto a((bc)d)\mapsto a(b(cd))$$
\begin{align} &\phantom{{}\mapsto{}}((af)e)(c(db))\\ &\mapsto (a(fe))(c(db))\\ &\mapsto (a(fe))((cd)b)\\ &\mapsto (a(fe))(b(cd))\\ &\mapsto (a(ef))(b(cd))\\ &\mapsto a((ef)(b(cd)))\\ &\mapsto a((b(cd))(ef))\\ &\mapsto a(b((cd)(ef)))\\ &\mapsto a(b(c(d(ef)))) \end{align}
There are $C_{n-1}\cdot n!$ possible trees on $n$ elements, and about $2n$ possible operations to apply at each stage, so the information theoretic bound gives $\Omega(\log_{2n}(C_{n-1}\cdot n!))=\Omega(n)$. On the other hand, if we first fully right associate, then we can perform adjacent swaps with $O(1)$ operations, leading to an upper bound of $O(n^2)$ operations.
I suspect that $O(n\log n)$ operations suffice, perhaps even $O(n)$, but I have not been able to improve on the above bounds. I know that $O(n)$ operations work if it is possible to perform exchanges in $O(1)$, but every element has its depth change by at most 1 per operation, so exchanges are rather expensive ($O(n)$) in this model. Probably we want to keep the tree balanced during the sorting, but assuming a balanced tree it's not clear how to sort effectively by block swaps.