title: How to sort three variables using at most two swaps?
body: <p>The following algorithm can sort three variables <code>x</code>, <code>y</code> and <code>z</code> of type <code>K</code> which are comparable using <code>operator&lt;</code>:</p>
  
  <pre><code>void sort2(K&amp; x, K&amp; y) {
     if(y &lt; x)
        swap(x, y);
  }      
  
  void sort3(K&amp; x, K&amp; y, K&amp; z) {
     sort2(x, y);
     sort2(y, z);
     sort2(x, y);
  }
  </code></pre>
  
  <p>This needs three swaps in the "worst case". However basic mathematics tells us, that the ordering of three values can be done using only two swaps.</p>
  
  <p>Example: The values (c,b,a) will be sorted using three swaps: (c,b,a) -> (b,c,a) -> (b,a,c) -> (a,b,c). However one swap would have been enough: (c,b,a) -> (a,b,c).</p>
  
  <p>What would be the simplest algorithms which sorts three variables with at most two swaps in all cases?</p>