The most efficient way to sort 3 numbers. It uses the exact minimum number of comparisons and assignments. It is hyper efficient with how it moves around the variables to sort the values, only creating a single external swap value. It is implemented as a Binary Insertion Sort, which has ideal comparisons, but not ideal assignments. However becau…

sort3.hpp

#ifndef SAM_BELLIVEAU_SORT_THREE
#define SAM_BELLIVEAU_SORT_THREE 1

/**
 * The most optimal way to sort 3 objects in terms
 * of memory usage, assignments, and comparisons.
 *
 * Can be used as a base function in bigger sorting 
 * algorithms
 */
template<class T>
void Sort3(T& i1, T& i2, T& i3)
{
    if(i1 < i2) // [i1 < i2, i3]
    { 
        if(i2 < i3) // [i1 < i2 < i3]
        {}

        else // [(i1, i3) < i2] 
        {
            if(i1 < i3) // [i1 < i3 < i2] {SORTED}
            {
                T t(i2);
                i2 = i3;
                i3 = t;
            }

            else // [i3 < i1 < i2] {SORTED}
            {
                T t(i1);
                i1 = i3;
                i3 = i2;
                i2 = t;
            }
        }
    }

    else // [i2 < i1, i3]
    {
        if(i1 < i3) // [i2 < i1 < i3] {SORTED}
        {
            T t(i1);
            i1 = i2;
            i2 = t;
        }

        else // [(i2, i3) < i1]
        {
            if(i2 < i3) // [i2 < i3 < i1] {SORTED}
            {   
                T t(i1);
                i1 = i2;
                i2 = i3;
                i3 = t;
            }
            else // [i3 < i2 < i1] {SORTED}
            {
                T t(i1);
                i1 = i3;
                i3 = t;
            }
        }
    }
}

#endif