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.