C++ – Quickly sort 3 values

algorithmarrayscsorting

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

Best Answer

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]);