Sorting Without Comparison

  1. You are given two numbers (a, b) and you wish to assign one each to (A, B) such that A<=B. That is, you want A to equal the minimum of a and b, and B to equal the maximum of a and b. How can you write A=f(a,b), and B=g(a,b,A) to correctly assign the values? Try to make functions f and g as simple as possible.
  2. Can you extend the above result for three original numbers (a, b, and c) to be assigned to A<=B<=C?
  3. Can you extend it to four numbers simply?
  4. Is there a general approach for more numbers, or is a repetitive method required?
Source: College homework problem.
Solutions were received from Ravi Subramanian, Philippe Fondanaiche, and Jonty Humphries. Philippe's solutions are below:
  1. Two terms a,b to be sorted according to A<=B. The simplest answers are:
  2. Three terms a,b,c to be sorted according to A<=B<=C.
  3. Four terms a,b,c,d to be sorted according to A<=B<=C<=D. It appears that A is equal to min[min(a,b),min(c,d)] and D is equal to max[max(a,b),max(c,d)]. Therefore B and C can be expressed through max[min(a,b),min(c,d)] and min[max(a,b),max(c,d)].

Mail to Ken