Design an efficient algorithm to sort 5 distinct keys in fewer than 8 comparisons

For sorting networks, it is not possible to have less than 9 comparisons to sort 5 items when the input is not known. The lower bound has been proven for sorting networks up to 10. See https://en.wikipedia.org/wiki/Sorting_network.

Correctness of sorting networks could be verified by the Zero-one principle as mentioned in The Art of Computer Programming, Vol 3 by Knuth. That is, if a sorting network can correctly sort all permutations of 0s and 1s, then it is a correct sorting network. None of the algorithms mentioned on this post passed the Zero-one test.

In addition, the lower bound says that comparison based sorts cannot have less than ceil(log(n!)) comparators to correctly sort, however, it does not mean that this is achievable.

Here is C++ implementation which sorts 5 elements in <= 7 comparisons. Was able to find 8 cases which can be sorted in 6 comparisons. That makes sense if we imagine full binary tree with 120 leaf nodes, there will be 112 nodes at level 7 and 8 leaf nodes at level 6. Here is the full code that is tested to work for all possible permutations.

#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <numeric>

using namespace std;

ostream& operator << ( ostream& os, vector<int> v )
{
    cout << "[ ";
    for ( auto x: v ) cout << x << ' ';
    cout << "]";
    return os;
}

class Comp {
    int count;
public:
    Comp(): count{0}{}
    bool isLess( vector<int> v, int i, int j ) {
        count++;
        //cout << v << "Comparison#" << count << ": " << i << ", " << j << endl;
        return v[ i ] < v[ j ];
    }
    int getCount() { return count; }
};


int mySort( vector<int> &v )
{
    Comp c;
    if ( c.isLess( v, 1, 0 ) ) {
        swap( v[ 0 ], v[ 1 ] );
    }
    if ( c.isLess( v, 3, 2 ) ) {
        swap( v[ 2 ], v[ 3 ] );
    }
    // By now (0, 1) (2, 3) (4)
    if ( c.isLess( v, 0, 2 ) ) {
        // ( 0, 2, 3 ) (1)
        swap( v[ 1 ], v[ 2 ] );
        swap( v[ 2 ], v[ 3 ] );
    } else {
        // ( 2, 0, 1 ) ( 3 )
        swap( v[ 1 ], v[ 2 ] );
        swap( v[ 0 ], v[ 1 ] );
    }
    // By now sorted order ( 0, 1, 2 ) ( 3 ) ( 4 ) and know that 3 > 0
    if ( c.isLess( v, 4, 1 ) ) {
        if ( c.isLess( v, 4, 0 ) ) {
            // ( 4, 0, 1, 2 ) ( 3 ) ( ... )
            v.insert( v.begin(), v[4] );
            // By now ( 0, 1, 2, 3 ) ( 4 ) ( ... ) and know that 4 > 1
            if ( c.isLess( v, 4, 2 ) ) {
                // ( 0, 1, 4, 2, 3 ) ( ... )
                v.insert( v.begin() + 2, v[4] );
            } else {
                if ( c.isLess( v, 4, 3 ) ) {
                    // ( 0, 1, 2, 4, 3 ) ( ... )
                    v.insert( v.begin() + 3, v[4] );
                } else {
                    // ( 0, 1, 2, 3, 4 ) ( ... )
                    v.insert( v.begin() + 4, v[4] );
                }
            }
            // ( 1 2 3 4 5 ) and trim the rest
            v.erase( v.begin()+5, v.end() );
            return c.getCount(); /////////// <--- Special case we could been done in 6 comparisons
        } else {
            // ( 0, 4, 1, 2 ) ( 3 ) ( ... ) 
            v.insert( v.begin() + 1, v[4] );
        }
    } else {
        if ( c.isLess( v, 4, 2 ) ) {
            // ( 0, 1, 4, 2 ) ( 3 ) ( ... )
            v.insert( v.begin() + 2, v[4] );
        } else {
            // ( 0, 1, 2, 4 ) ( 3 ) ( ... )
            v.insert( v.begin() + 3, v[4] );
        }
    }
    // By now ( 0, 1, 2, 3 ) ( 4 )( ... ): with 4 > 0
    if ( c.isLess( v, 4, 2 ) ) {
        if ( c.isLess( v, 4, 1 ) ) {
            // ( 0, 4, 1, 2, 3 )( ... )
            v.insert( v.begin() + 1, v[4] );
        } else {
            // ( 0, 1, 4, 2, 3 )( ... )
            v.insert( v.begin() + 2, v[4] );
        }
    } else {
        if ( c.isLess( v, 4, 3 ) ) {
            // ( 0, 1, 2, 4, 3 )( ... )
            v.insert( v.begin() + 3, v[4] );
        } else {
            // ( 0, 1, 2, 3, 4 )( ... )
            v.insert( v.begin() + 4, v[4] );
        }
    }
    v.erase( v.begin()+5, v.end() );
    return c.getCount();
}

#define TEST_ALL
//#define TEST_ONE

int main()
{
#ifdef TEST_ALL
    vector<int> v1(5);
    iota( v1.begin(), v1.end(), 1 );
    do {
        vector<int> v2 = v1, v3 = v1;
        int count = mySort( v2 );
        if ( count == 6 )
            cout << v3 << " => " << v2 << " #" << count << endl;
    } while( next_permutation( v1.begin(), v1.end() ) );
#endif

#ifdef TEST_ONE
    vector<int> v{ 1, 2, 3, 1, 2};
    mySort( v );
    cout << v << endl;
#endif
}