The Schensted insertion algorithm has an $O(n^2)$ running time, for constructing such a standard Young's Tableaux.
But, since every permutation has a unique Young's tableau, there seems no reason as to why it cannot be done in $O(n \log n)$ time, which is the optimal time to identify a permutation.
Are there any known non-trivial lower bounds for this?
Any assistance/guidance towards any of the questions is much appreciated. Thanks in advance
Sample input permutation
Output Young's Tableaux