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: 
I recently had to solve a similar problem - sort three values efficiently. You concentrate on swap-operations in your question. If performance is what you are looking for, concentrate on the comparison operations and branches! When sorting such a "tiny" array with just three values, a good idea is to consider using additional storage, which is appropriate for so few values. I came up with something like a specialized "merge sort" (see code below).

Just as **tenfour** suggests, I looked at the assembly, and the code below compiles down to a compact inline set of CPU-register operations, and is extremely fast. The additional variable "arr12" is also stored in the CPU-registers. The sorting requires two or three comparison operations. The function can easily be converted to a template (not given here for clarity).

```
inline void sort3_descending( double * arr )
{
    double  arr12[ 2 ];

    // sort first two values
    if( arr[ 0 ] > arr[ 1 ] )
    {
        arr12[ 0 ] = arr[ 0 ];
        arr12[ 1 ] = arr[ 1 ];
    } // if
    else
    {
        arr12[ 0 ] = arr[ 1 ];
        arr12[ 1 ] = arr[ 0 ];
    } // else

    // decide where to put arr12 and the third original value arr[ 3 ]
    if( arr12[ 1 ] > arr[ 2 ] )
    {
        arr[ 0 ] = arr12[ 0 ];
        arr[ 1 ] = arr12[ 1 ];
    } // if
    else if( arr[ 2 ] > arr12[ 0 ] )
    {
        arr[ 0 ] = arr  [ 2 ];
        arr[ 1 ] = arr12[ 0 ];
        arr[ 2 ] = arr12[ 1 ];
    } // if
    else
    {
        arr[ 0 ] = arr12[ 0 ];
        arr[ 1 ] = arr  [ 2 ];
        arr[ 2 ] = arr12[ 1 ];
    } // else
}

```
This can illustrated with a truth table relating to every possible combination of comparisons to see how we can best optimize the swap you mention here.

Values | x < y | y < z | x < z

x,y,z | y | y | y

x,z,y | y | n | y

y,x,z | n | y | y

y,z,x | n | y | n

z,x,y | y | n | n

z,y,x | n | n | n

By framing the question this way, we can easily see that by initially checking and swapping the 1st and 3rd element, the lowest value that we can have in the first element after the swap can either be x or y. This simplifies the if check afterwards so that we can either swap the 1st and 2nd element when x > y or swap the 2nd and 3rd element when y > z.

```
if (x > z) {
    swap(x,z);
}

if (x > y) {
    swap(x,y);
} else if (y > z) {
    swap(y,z);
}

```

No need for any nested if conditionals. Just 2-3 simple comparisons for 2 swaps at max.