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: 
### 2 to 3 comparisons, 0 to ~1.7 swaps

Old question, new answer... The following algorithm sorts `x`, `y` and `z` with 2 to 3 comparisons depending on their values and 0 to ~1.7 swap operations.

```
void sort3(K& x, K& y, K& z)
{    
    if (y < x) {
        if (z < x) {
            if (z < y) {
                swap(x, z);
            } else {
                K tmp = std::move(x);
                x = std::move(y);
                y = std::move(z);
                z = std::move(tmp);
            }
        } else {
            swap(x, y);
        }
    } else {
        if (z < y) {
            if (z < x) {
                K tmp = std::move(z);
                z = std::move(y);
                y = std::move(x);
                x = std::move(tmp);
            } else {
                swap(y, z);
            }
        }
    }
}

```

So, how does it work? It's basiccaly an unrolled insertion sort: if the values are already sorted (it takes 2 comparisons to check that) then the algorithm does not swap anything. Otherwise, it performs 1 or 2 swap operations. However, when 2 swap operations are required, the algorithm « rotates » the values instead so that 4 moves are performed instead of 6 (a swap operation should cost 3 moves, [unless optimized](https://stackoverflow.com/a/8617483/1364752)).

There are only 6 possible permutations of 3 values. This algorithm does the comparisons needed to know which permutation we're treating. Then it does the swapping and leaves. Therefore, the algorithm has 6 possible paths (including the one where it does nothing because the array is already sorted). While it's still human-readable, an equivalently optimal algorithm to sort 4 values would have 24 different paths and would be much harder to read (for n values, there are n! possible permutations).

Since we're already in 2015 and you seemed to be using C++, I took the liberty use [`std::move`](http://en.cppreference.com/w/cpp/utility/move) so to make sure that the swap-rotate thingy would be efficient enough and would work even for moveable but non-copyable types.
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.