Sorting a Sequence 3

Only cyclic shifts are reachable. Count cyclic descents, including the comparison from $A_N$ to $A_1$. A sorted shift exists exactly when this count is at most one: cut the cycle at that descent. This takes $O(N)$ time; checking all rotations takes $O(N^2)$.