Q: Lambert's O(n^2) algorithm on pairwise sum sort Sorting Pairwise Sums of X and Y with O(n^2) comparisons are quite hard.
http://cs.smith.edu/~orourke/TOPP/P41.html
http://en.wikipedia.org/wiki/X_%2B_Y_sorting
It seems Lambert has concluded that if some non-comparison operations are allowed, then it is achievable. 
I can find his original paper: http://www.sciencedirect.com/science/article/pii/030439759290089X
Also I found a functional approach for his algorithm.

However, I really don't understand even after several times of attempts.
So what I roughly know is his algorithm tries:


*

*tag element with its original index

*negate it

*using the equation of X - Y < X' - Y' == X - X' < Y - Y'. 


Other than that I am totally lost.

So anyone here really understands that algorithm? Can anyone clearly explain it in a simple way?
