3 edited body
source | link

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.


  1. 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.


  1. 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.


  1. Sorting and Searching by Donald E. Knuth; The Art of Computer Programming Vol. 3 (2nd ed, 1998)
2 adds proof of comparison-optimality
source | link

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  .


  1. 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.


  1. Sorting and Searching by Donald E. Knuth; The Art of Computer Programming Vol. 3 (2nd ed, 1998)
1
source | link

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 .