In randomized input with uniform statistics, should be on average (n - log n) which also gives a handle on theta notation complexity.