Yes, if the data is not already sorted. Thus it's O(n) for already sorted data and O(n log(n) + n) -- which simplifies to O(n log(n)) -- for arbitrary data.
Yeah. I know. Why would the data already be sorted?
In a database you might have already built an index on that data.