In C++11, std::sort is supposed to be able to sort collections of mve-only types. This patch adds support for move-only types to timsort. Here is what it changes:

• More GFX_TIMSORT_MOVE instead of simple copy-assignments.
• Introduce GFX_TIMSORT_MOVE_RANGE to use the C++11 iterators version of std::move if required and us std::copy instead.
• Introduce GFX_TIMSORT_MOVE_BACKWARD to use either std::move_backward or std::copy_backward.
• I also fixed a mistake in an assert message, but that's trivial :p

However, here is the big deal: I am not 100% sure that the algorithm never reads from a moved-from value. I read the algorithm and checked everywhere that whenever a value was moved-from the algorithm made sure that the iterators point to other non-moved-from values before being dereferenced, but this method has its limits. I also used a derived version of the benchmarks from my sorting library with a move-only type that keeps track of whether it has been moved-from and asserts if we try to read from it if it has been moved-from. Here is the type I used:

template<typename T>
struct move_only
{
    // Constructors

    move_only() = delete;
    move_only(const move_only&) = delete;

    move_only(const T& value):
        can_read(true),
        value(value)
    {}

    move_only(move_only&& other):
        can_read(true),
        value(std::move(other.value))
    {
        if (not std::exchange(other.can_read, false))
        {
            std::cerr << "illegal read from a moved-from value\n";
            assert(false);
        }
    }

    // Assignment operators

    move_only& operator=(const move_only&) = delete;

    auto operator=(move_only&& other)
        -> move_only&
    {
        if (&other != this)
        {
            if (not std::exchange(other.can_read, false))
            {
                std::cerr << "illegal read from a moved-from value\n";
                assert(false);
            }
            can_read = true;
            value = std::move(other.value);
        }
        return *this;
    }

    // Whether the value can be read
    bool can_read;
    // Actual value
    T value;
};

The benchmark runs several times on arrays of one million element with several data patterns to cover common and not-so-common cases, including arrays filled with random values. After every call to a sort method, it also checks that the resulting array is indeed sorted.

So, while I couldn't be 100% sure that it never reads from moved-from value (it would require a formal analysis), check the algorithm by hand and running all those tests make me pretty confident that it is safe :)

I didn't write a proper test case though since all of your tests seem to work with C++03, and such a test would explicitly require C++11 support to run and I don't know whether it would integrate seamlessly in the testsuite.