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.

  • $\begingroup$ Why the downvotes? $\endgroup$ – gigabytes Jun 15 at 12:53
  • $\begingroup$ 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? $\endgroup$ – araomis Jun 15 at 19:26
  • $\begingroup$ 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. $\endgroup$ – Neal Young Jun 17 at 14:28
  • 1
    $\begingroup$ @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. $\endgroup$ – Neal Young Jun 17 at 14:30
  • $\begingroup$ Right. Your interpretation makes sense to me. $\endgroup$ – araomis Jun 17 at 14:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.