## Generic Mergesort

A few month ago I wrote several basic sort algorithm for educational purposes as generic as possible in C++. Here I want to present an Generic Mergesort:

1 2 3 4 5 6 7 8 9 |
template <typename I> void merge(I first, I mid, I last) { while (first != mid && mid != last) { auto iter = mid; first = std::upper_bound(first, mid, *mid); mid = std::upper_bound(mid, last, *first); std::rotate(first, iter, mid); } } |