Is there a polynomial algorithm for optimal sorting on trees?
This problem is called Token Swapping, and you can find more information if you search by its name on google.

I couldn't find a proof that it is NP-complete on trees, but I've found a recent paper that gives a 2-approximation algorithm for trees:
http://erikdemaine.org/papers/TokenReconfiguration_FUN2014/paper.pdf