Comment by saagarjha

Assuming constantly time comparison, the best you are going to be able to do is log(n!), which is O(n log n) by Stirling's approximation. But comparing a permutation is likely to be O(n), so you'll probably do worse than that.