Sorting Pairwise Sums of X+Y with O(n^2) comparisons is a hard problem: 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
Additionally, I found a functional approach for his algorithm.
However, I really don't understand how the algorithm works, even after several attempts.
What I know so far about how the algorithm works:
- 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 lost.
Does anyone here really understand that algorithm? Can anyone clearly explain it in a simple way, and particularly how we use step 3 above?