The Fastest Sorting Algorithm?

If the sequence x(1), x(2), ..., x(2k) is bitonic,
the two sequences

  L = min(x(1), x(k+1)), min(x(2), x(k+2)), min(x(k), x(2k))

and
  R = max(x(1), x(k+1)), max(x(2), x(k+2)), max(x(k), x(2k))


are also bitonic. Furthermore, each element of L is smaller
than or equal to each element of R.

Figure 5: The bitonic lemma.