The complexity is obviously nlogn - it's just hard to prove (this comment is only somewhat serious)