Quickly sort 3 values

Question

I have an array of three floating-point values and I want to sort them in ascending order (although order of perhaps any sorting algorithm can be easily reversed). Calling std::sort seems like an overkill:

float values[3] = {...};
std::sort(values, values + 3);

You could do something like:

float sorted[3] = {min(values), values[0] + values[1] + values[2] -
    min(values) - max(values), max(values)};

But that seems plain ugly. Also adding and subtracting of the numbers may change value of the middle sorted element. And it does not easily work in-place. Also interesting:

float sorted[3];
/*for(int i = 0; i < 3; ++ i) { // unroll
    sorted[(values[i] > values[0]) + (values[i] > values[1]) +
        (values[i] > values[2])] = values[i];
}*/ // this is broken, does not work if two or all values are equal
sorted[(values[0] > values[1]) + (values[0] > values[2])] = values[0];
sorted[(values[1] >= values[0]) + (values[1] > values[2])] = values[1];
sorted[(values[2] >= values[0]) + (values[2] >= values[1])] = values[2];

But that kind of depends on how the comparison result can be converted to an integer (probably comparison + flag load instruction). Also depends on how the compiler optimizes away comparison of each element with itself, which is not easy if you consider special floating point values. Does not work inplace either.

#define cswap(a,b) do { if(a > b) { float tmp = a; a = b; b = tmp; } } while(0)
cswap(values[0], values[1]);
cswap(values[1], values[2]);
cswap(values[0], values[1]);

There could be a sorting network, but i suppose that is not optimal for sorting other than powers of two of elements. Only three elements ... seems like there should be a really easy way to do it, but maybe there is none.

What would be the minimal and at the same time fast way to sort three numbers? Readability is not a concern here.

This is kind of similar to Fastest sort of fixed length 6 int array but here I would expect some short but quick code, as sorting 3 values can likely be written in fewer lines of code than a sorting loop for arbitrary number of items.

Results:

Measured on 100 billions of numbers on Intel Core i7-2620M and Windows 7. Visual Studio 2008, release, the numbers were generated with rand(), but the time spent inside was subtracted.

std::sort method: 3.510 sec
min/max method: 2.964 sec
comparison insertion: 2.091 sec (the fixed version, 2.292 for the buggy one)
sort3() by Jarod42: 1.966 sec
sorting network: 1.903 sec

Answer 1

The general algorithm is:

if (a[0] > a[1])
    swap(a[0], a[1]);
if (a[0] > a[2])
    swap(a[0], a[2]);
if (a[1] > a[2])
    swap(a[1], a[2]);

Answer 2

There are only 6 possible permutations, so you could just write a bunch of nested conditions to get all the possibilities. See, e.g., here. On the other hand, something simple but more general like insertion sort is efficient for small arrays. Insertion sort is also used as an optimization for sorting smaller arrays in quicksort. So you'd expect it to be used in std::sort.

Indeed, I just debugged into std::sort and that uses insertion sort for smaller arrays on my implementation (VC++2012). If the size of the array was known to be 3 at compile time it is a fair bet that the generated code would be fairly optimal. I would therefore stick with std::sort unless there is a very strong reason to optimize.

Answer 3

In case I didn't use std::sort, I would use:

template <typename T>
void sort3(T (&a)[3])
{
    if (a[0] < a[1]) {
        if (a[1] < a[2]) {
            return;
        } else if (a[0] < a[2]) {
            std::swap(a[1], a[2]);
        } else {
            T tmp = std::move(a[0]);
            a[0] = std::move(a[2]);
            a[2] = std::move(a[1]);
            a[1] = std::move(tmp);
        }
    } else {
        if (a[0] < a[2]) {
            std::swap(a[0], a[1]);
        } else if (a[2] < a[1]) {
            std::swap(a[0], a[2]);
        } else {
            T tmp = std::move(a[0]);
            a[0] = std::move(a[1]);
            a[1] = std::move(a[2]);
            a[2] = std::move(tmp);
        }
    }
}

Answer 4

sort3 from @Jarod42 is a better algorithm (an this is the network algorithm) than the "general" algorithm (from Jim Mischel) because it can save one comparison when a[0] < a[1] && a[1]<a[2] you don't have to compare a[0] vs a[2]. More over you can compute the 2 comparison operations a[0] < a[1] and a[1] < a[2] in parallel. Saving comparisons (and running some in parallel) is the purpose of these network sorting algorithms.

In fact Jim Mischel's algorithm is the bubble sort algorithm.

Answer 5

if (Value1 < Value2)
    {
        if (Value1 < Value3)
        {
            if (Value2 < Value3)
            {
                First = Value1;
                Second = Value2;
                Third = Value3;
            }
            else
            {
                First = Value1;
                Second = Value3;
                Third = Value2;
            }
        }
        else // Value3 < Value1
        {
            First = Value3;
            Second = Value1;
            Third = Value2;
        }
    }
    else // Value2 < Value1
    {
        if (Value2 < Value3)
        {
            if (Value1 < Value3)
            {
                First = Value2;
                Second = Value1;
                Third = Value3;
            }
            else
            {
                First = Value2;
                Second = Value3;
                Third = Value1;
            }
        }
        else //Value3 < Value2
        {
            First = Value3;
            Second = Value2;
            Third = Value1;
        }
    }