Question: The following algorithm can sort three variables `x`, `y` and `z` of type `K` which are comparable using `operator<`:

```
void sort2(K& x, K& y) {
   if(y < x)
      swap(x, y);
}      

void sort3(K& x, K& y, K& z) {
   sort2(x, y);
   sort2(y, z);
   sort2(x, y);
}

```

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.

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

What would be the simplest algorithms which sorts three variables with at most two swaps in all cases?

Answer: 
```
void sort(int& a, int& b, int& c)
{
   swap(a, min(a, min(b, c)));
   swap(b, min(b, c));
}

```

2 swaps, 3 comparisons.
I think what you want is to find the optimal swap in each step instead of just a valid swap. To do that, just find the greatest difference between an element and an element later in the list and swap those. In a 3-tuple, there are three possible swaps, 1-3, 1-2, and 2-3. At each step find the max difference among these three swaps and do that. Pretty sure that gives two swaps in the worst case for 3 elements. Only really makes sense if swapping is relatively expensive compared to comparing elements, otherwise probably not worth the additional analysis upfront.