3 edited body edited Feb 26 '15 at 15:23 Raphael♦ 59k2525 gold badges144144 silver badges327327 bronze badges Just so that it's on the table, here's a direct algorithm: // Sort x1, x2 if x1 < x2 M1 = x2 m1 = x1 else M1 = x1 m1 = x2 end // Sort x3, x4 if x3 < x4 M2 = x4 m2 = x3 else M2 = x3 m2 = x4 end // Pick largest two if M1 > M2 M3 = M1 if m1 > M2 m3 = m1 else m3 = M2 end else M3 = M2 if m2 > M1 m3 = m2 else m3 = M1 end end // Insert x4 if x4 > M3 m3 = M3 M3 = x4 else if x4 > m3 m3 = x4 end  By clever implementation of if ... else, one can get rid of some unconditional jumps a direct translation would have. This is ugly but takes only five or six comparisons (i.e. conditional jumps), nine to ten assignments (with 11 variables, all in registers) and no additional memory access. In fact, six comparisons is optimal for this problem as Theorem S in section 5.3.3 of [1] shows; here we need $$V_2(5)$$$$W_2(5)$$. This can not be expected to be fast on machines with pipelining, though; given they high percentage of conditional jumps, most time would probably be spent in stall. Note that a simpler variant -- sort x1 and x2, then insert the other values subsequently -- takes four to seven comparisons and only five to six assignments. Since I expect jumps to be of higher cost here, I stuck with this one. Sorting and Searching by Donald E. Knuth; The Art of Computer Programming Vol. 3 (2nd ed, 1998) Just so that it's on the table, here's a direct algorithm: // Sort x1, x2 if x1 < x2 M1 = x2 m1 = x1 else M1 = x1 m1 = x2 end // Sort x3, x4 if x3 < x4 M2 = x4 m2 = x3 else M2 = x3 m2 = x4 end // Pick largest two if M1 > M2 M3 = M1 if m1 > M2 m3 = m1 else m3 = M2 end else M3 = M2 if m2 > M1 m3 = m2 else m3 = M1 end end // Insert x4 if x4 > M3 m3 = M3 M3 = x4 else if x4 > m3 m3 = x4 end  By clever implementation of if ... else, one can get rid of some unconditional jumps a direct translation would have. This is ugly but takes only five or six comparisons (i.e. conditional jumps), nine to ten assignments (with 11 variables, all in registers) and no additional memory access. In fact, six comparisons is optimal for this problem as Theorem S in section 5.3.3 of [1] shows; here we need $$V_2(5)$$. This can not be expected to be fast on machines with pipelining, though; given they high percentage of conditional jumps, most time would probably be spent in stall. Note that a simpler variant -- sort x1 and x2, then insert the other values subsequently -- takes four to seven comparisons and only five to six assignments. Since I expect jumps to be of higher cost here, I stuck with this one. Sorting and Searching by Donald E. Knuth; The Art of Computer Programming Vol. 3 (2nd ed, 1998) Just so that it's on the table, here's a direct algorithm: // Sort x1, x2 if x1 < x2 M1 = x2 m1 = x1 else M1 = x1 m1 = x2 end // Sort x3, x4 if x3 < x4 M2 = x4 m2 = x3 else M2 = x3 m2 = x4 end // Pick largest two if M1 > M2 M3 = M1 if m1 > M2 m3 = m1 else m3 = M2 end else M3 = M2 if m2 > M1 m3 = m2 else m3 = M1 end end // Insert x4 if x4 > M3 m3 = M3 M3 = x4 else if x4 > m3 m3 = x4 end  By clever implementation of if ... else, one can get rid of some unconditional jumps a direct translation would have. This is ugly but takes only five or six comparisons (i.e. conditional jumps), nine to ten assignments (with 11 variables, all in registers) and no additional memory access. In fact, six comparisons is optimal for this problem as Theorem S in section 5.3.3 of [1] shows; here we need $$W_2(5)$$. This can not be expected to be fast on machines with pipelining, though; given they high percentage of conditional jumps, most time would probably be spent in stall. Note that a simpler variant -- sort x1 and x2, then insert the other values subsequently -- takes four to seven comparisons and only five to six assignments. Since I expect jumps to be of higher cost here, I stuck with this one. Sorting and Searching by Donald E. Knuth; The Art of Computer Programming Vol. 3 (2nd ed, 1998) 2 adds proof of comparison-optimality edited Feb 25 '15 at 11:19 Raphael♦ 59k2525 gold badges144144 silver badges327327 bronze badges Just so that it's on the table, here's a direct algorithm: // Sort x1, x2 if x1 < x2 M1 = x2 m1 = x1 else M1 = x1 m1 = x2 end // Sort x3, x4 if x3 < x4 M2 = x4 m2 = x3 else M2 = x3 m2 = x4 end // Pick largest two if M1 > M2 M3 = M1 if m1 > M2 m3 = m1 else m3 = M2 end else M3 = M2 if m2 > M1 m3 = m2 else m3 = M1 end end // Insert x4 if x4 > M3 m3 = M3 M3 = x4 else if x4 > m3 m3 = x4 end  By clever implementation of if ... else, one can get rid of some unconditional jumps a direct translation would have. This is ugly but takes only five or six comparisons (i.e. conditional jumps), nine to ten assignments (with 11 variables, all in registers) and no additional memory access. In fact, six comparisons is optimal for this problem as Theorem S in section 5.3.3 of [1] shows; here we need $$V_2(5)$$. This can not be expected to be fast on machines with pipelining, though; given they high percentage of conditional jumps, most time would probably be spent in stall. Note that a simpler variant -- sort x1 and x2, then insert the other values subsequently -- takes four to seven comparisons and only five to six assignments. Since I expect jumps to be of higher cost here, I stuck with this one  . Sorting and Searching by Donald E. Knuth; The Art of Computer Programming Vol. 3 (2nd ed, 1998) Just so that it's on the table, here's a direct algorithm: // Sort x1, x2 if x1 < x2 M1 = x2 m1 = x1 else M1 = x1 m1 = x2 end // Sort x3, x4 if x3 < x4 M2 = x4 m2 = x3 else M2 = x3 m2 = x4 end // Pick largest two if M1 > M2 M3 = M1 if m1 > M2 m3 = m1 else m3 = M2 end else M3 = M2 if m2 > M1 m3 = m2 else m3 = M1 end end // Insert x4 if x4 > M3 m3 = M3 M3 = x4 else if x4 > m3 m3 = x4 end  By clever implementation of if ... else, one can get rid of some unconditional jumps a direct translation would have. This is ugly but takes only five or six comparisons (i.e. conditional jumps), nine to ten assignments (with 11 variables, all in registers) and no additional memory access. This can not be expected to be fast on machines with pipelining, though; given they high percentage of conditional jumps, most time would probably be spent in stall. Note that a simpler variant -- sort x1 and x2, then insert the other values subsequently -- takes four to seven comparisons and only five to six assignments. Since I expect jumps to be of higher cost here, I stuck with this one  . Just so that it's on the table, here's a direct algorithm: // Sort x1, x2 if x1 < x2 M1 = x2 m1 = x1 else M1 = x1 m1 = x2 end // Sort x3, x4 if x3 < x4 M2 = x4 m2 = x3 else M2 = x3 m2 = x4 end // Pick largest two if M1 > M2 M3 = M1 if m1 > M2 m3 = m1 else m3 = M2 end else M3 = M2 if m2 > M1 m3 = m2 else m3 = M1 end end // Insert x4 if x4 > M3 m3 = M3 M3 = x4 else if x4 > m3 m3 = x4 end  By clever implementation of if ... else, one can get rid of some unconditional jumps a direct translation would have. This is ugly but takes only five or six comparisons (i.e. conditional jumps), nine to ten assignments (with 11 variables, all in registers) and no additional memory access. In fact, six comparisons is optimal for this problem as Theorem S in section 5.3.3 of [1] shows; here we need $$V_2(5)$$. This can not be expected to be fast on machines with pipelining, though; given they high percentage of conditional jumps, most time would probably be spent in stall. Note that a simpler variant -- sort x1 and x2, then insert the other values subsequently -- takes four to seven comparisons and only five to six assignments. Since I expect jumps to be of higher cost here, I stuck with this one. Sorting and Searching by Donald E. Knuth; The Art of Computer Programming Vol. 3 (2nd ed, 1998) 1 answered Feb 25 '15 at 8:05 Raphael♦ 59k2525 gold badges144144 silver badges327327 bronze badges Just so that it's on the table, here's a direct algorithm: // Sort x1, x2 if x1 < x2 M1 = x2 m1 = x1 else M1 = x1 m1 = x2 end // Sort x3, x4 if x3 < x4 M2 = x4 m2 = x3 else M2 = x3 m2 = x4 end // Pick largest two if M1 > M2 M3 = M1 if m1 > M2 m3 = m1 else m3 = M2 end else M3 = M2 if m2 > M1 m3 = m2 else m3 = M1 end end // Insert x4 if x4 > M3 m3 = M3 M3 = x4 else if x4 > m3 m3 = x4 end  By clever implementation of if ... else, one can get rid of some unconditional jumps a direct translation would have. This is ugly but takes only five or six comparisons (i.e. conditional jumps), nine to ten assignments (with 11 variables, all in registers) and no additional memory access. This can not be expected to be fast on machines with pipelining, though; given they high percentage of conditional jumps, most time would probably be spent in stall. Note that a simpler variant -- sort x1 and x2, then insert the other values subsequently -- takes four to seven comparisons and only five to six assignments. Since I expect jumps to be of higher cost here, I stuck with this one .