Open main menu

Wikibooks β

Algorithm Implementation/Sorting/Binary Tree Sort

< Algorithm Implementation‎ | Sorting


#include <set>       // for multiset
#include <algorithm> // for copy
template <typename Iterator>
void binary_tree_sort(Iterator begin, Iterator end)
    // C++'s multiset class is a self-balancing binary search tree that allows duplicates
    // Add each element in input range to the tree
    std::multiset<typename std::iterator_traits<Iterator>::value_type> tree(begin, end);

    // Read elements in ascending order by simply traversing the tree.
    std::copy(tree.begin(), tree.end(), begin);