<p>If one has an algorithm that can sort a list of objects, then one can compare any two objects by applying the algorithm recursively to the set of just those two objects and seeing if the output of the algorithm is different from the input.  So it doesn't seem that there is any meaningful way one can sort without effectively having a pairwise comparison operation as a precondition.</p>

CC BY-SA 4.0
2020-02-09T14:21:33.763Z
2020-02-09T14:21:33.763Z
Dale
<p>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?</p>

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

CC BY-SA 4.0
2019-06-15T19:26:33.547Z
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?
sebastian
CC BY-SA 4.0
2019-06-17T14:28:07.823Z
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.
Neal Young
CC BY-SA 4.0
2019-06-17T14:30:03.197Z
@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.
Neal Young
CC BY-SA 4.0
2019-06-17T14:51:33.620Z
Right. Your interpretation makes sense to me.
sebastian
CC BY-SA 4.0
2019-06-17T15:30:10.000Z
@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!
multiplex
<cc.complexity-theory><ds.algorithms><sorting>
Is it possible to sort by only knowing the sign of pairwise sums?
multiplex
# Is it possible to sort by only knowing the sign of pairwise sums?

(Asked by: username_0 on 2019-06-14)

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.

**Tags:** cc.complexity-theory, ds.algorithms, sorting

> **Comments:**
> **username_1**: 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?  
> **username_2**: 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.  
> **username_2**: @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.  
> **username_1**: Right. Your interpretation makes sense to me.  
> **username_0**: @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!  

---

## 1 answers

### Answer by username_3 on 2020-02-09. Score: 1

If one has an algorithm that can sort a list of objects, then one can compare any two objects by applying the algorithm recursively to the set of just those two objects and seeing if the output of the algorithm is different from the input. So it doesn't seem that there is any meaningful way one can sort without effectively having a pairwise comparison operation as a precondition.


---

