What term can I use to describe something with O(N log N) complexity?
O(log N): Logarithmic
O(N log N): ??????
There is a jargon term linearithmic meaning exactly this.
I don't believe that it's universally understood by all programmers, so if you're not careful then it will obscure more than it informs. Personally I don't normally use it, and if I did then I'd probably define it on first use, for example "this article considers linearithmic (
O(N log N)) algorithms".
It is sometimes called "loglinear", although that word actually means something different. I would just stick with "N log N", though, as @Philip's answer suggests.