Question: is nlogn faster than n^2?
Answer: Just ask wolframalpha if you have doubts. That means n^2 grows faster, so n log(n) is smaller (better), when n is high enough. So, O(N*log(N)) is far better than O(N^2) . It is much closer to O(N) than to O(N^2) .