[math-fun] Optimally sorting a cyclic group

Suppose you have N records in which one of the fields is a number 0..(N-1), and there is exactly one record for each number 0..(N-1). It is trivial to sort such a set using traditional Knuth-TAOCP algorithms. However, if I don't care that the first record is labelled "0", but only care that the final ordering preserves the *cyclic* ordering of the group, can I do any better? Obviously, I can't do a lot better, since cyclicly rotating the ordering costs O(N), while sorting costs O(NlogN), but is there a clever way to sort w/o putting "0" at the front and "(N-1)" at the end? In particular, is there a way to sort that automatically notices when the records are already in cyclic order, and doesn't bother making any further changes.