OP here - O(N log N) is not O(n^2). If n is 1000 then log n is 10, which is 1000 * 10 which is 10,000. That's a bit less than 1000 * 1000.
Also the fact that you're plugging numbers in for n indicates to me that you don't actually understand big O notation, which is surprising since the original article is decent.
[0] https://en.wikipedia.org/wiki/Big_O_notation#Formal_definiti...