Given $n$ points in 2D, e.g., $p_1,p_2,....,p_n$, there are $n^2$ possible pairs of points. I want to output the list of $n^2$ pairs, but sorted according to their distance (e.g., the pair of two points that are closest is the first pair in the output, and so on).
Is there an algorithm to do this with running time better than $O(n^2 \log n)$? If there was no metric property and the "distance" of each pair of points was unrelated to all other distances, the lower bound would be $\Omega(n^2 \log n^2)$ based on the lower bound for sorting $n^2$ values, but perhaps we can use the properties of the Euclidean distance to do better?