# Is it possible to sort by only knowing the sign of pairwise sums?

I am currently thinking of how much structure one actually needs in order to be able to sort things at all. All comparison-based algorithms need a direct comparability, but are we able to remove this necessity and only operate on the sign of the sum of two elements which we are comparing right now?

This surely does not work for the general case, but what if we have a set of numbers and its complements for example.

• Since $x > y \iff x - y > 0$ it is clear that if you can get the sign of the sum of two elements and if you do have the additive inverse of every element then you can do it. Or is there something I missed from your question? Commented Jun 15, 2019 at 19:26
• This seems like a nice homework exercise. I assume by "a set of numbers and its complements" you mean your set of numbers is closed under negation. So, find the minimum and the maximum numbers: a number is the maximum (minimum) iff its sum with every other number in the set is non-negative (non-positive). So, find the minimum and the maximum, remove those, then recurse. Commented Jun 17, 2019 at 14:28
• @araomis Perhaps you aren't given which pairs of numbers are additive inverses of each other, but I guess you can find the additive inverse of a given element x by finding the element y such that x+y is zero. Then your method works. Commented Jun 17, 2019 at 14:30
• Right. Your interpretation makes sense to me. Commented Jun 17, 2019 at 14:51
• @NealYoung is right with his assumption. I actually found a way to not sort them explicitly and reduce the complexity to Theta(nlogn) instead of Theta(N^2). Thank y'all for your input nevertheless! Commented Jun 17, 2019 at 15:30