Bogosort.cpp

gistfile1.cpp

template < typename container_t >

void BogoSort( container_t & data )
{
    using std::begin;
    using std::end;
    
    std::random_device rd;
    std::mt19937       ung( rd() );
    
    while( !std::is_sorted(begin(data), end(data)) )
    {
        std::shuffle(begin(data), end(data), ung);
    }
}

The best case is still O(n), since it takes linear time to check whether the input is sorted.

Now make it a stable sort.. 8)