Aus Spaß habe ich den einfachsten vorstellbaren Sortieralgorithmus implementiert:

template<typename Iterator>
void treesort(Iterator begin, Iterator end)
{
    typedef typename std::iterator_traits<Iterator>::value_type element_type;

    // copy data into the tree
    std::multiset<element_type> tree(begin, end);

    // copy data out of the tree
    std::copy(tree.begin(), tree.end(), begin);
}

Es ist nur etwa 20 mal langsamer alsstd::sort für meine Testdaten :)

Als nächstes wollte ich die Leistung mit der Bewegungssemantik verbessern:

template<typename Iterator>
void treesort(Iterator begin, Iterator end)
{
    typedef typename std::iterator_traits<Iterator>::value_type element_type;

    // move data into the tree
    std::multiset<element_type> tree(std::make_move_iterator(begin),
                                     std::make_move_iterator(end));
    // move data out of the tree
    std::move(tree.begin(), tree.end(), begin);
}

Aber das hat die Leistung nicht wesentlich beeinflusst, obwohl ich sortierestd::strings.

Dann erinnerte ich mich, dass assoziative Container von außen konstant sind, das heißt,std::move undstd::copy wird hier dasselbe tun :( Gibt es eine andere Möglichkeit, die Daten aus dem Baum zu verschieben?