I've seen couple of guys (@Hewitt_1570, @realhly88) claim this can be done in nlogn. So, can that? code is hairy.
Given, O(n^2) (or, rather, O(n * (n-1)) is well known, and well understood,
anyone care to explain O(n * log n) possible (or prove otherwise)? Hence this thread.
I've added some further prove to the original post please check it out if still interested.