A few month ago I wrote several basic sort algorithm for educational purposes as generic as possible in C++. In a few days time I want to present some of that stuff in my class but before that I thought I show my implementation to you and listen to your comments of what do you find confusing or very readable.
Mergesort
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);
}
}
What did I do here? Very simple; I want to avoid to allocate any new memory actively myself and try to write readable algorithm with as few loops as possible.
Obviously, I could not use the 'standard' way implementing merge not very readable. I also needed an in-place looking variant. So I started at looking what I actually do if I try to merge something in itself, what mergesort does in the end.
According to the STL documentation, std::upper_bound does the following:
Returns an iterator pointing to the first element in the range [first, last) that is greater than value, or last if no such element is found. The range [first, last) must be at least partially ordered, i.e. partitioned with respect to the expression !(value < element) or !comp(value, element). A fully-sorted range meets this criterion. The first version uses operator< to compare the elements, the second version uses the given comparison function comp.
I call this function twice, first to receive an Iterator of the first part of my array which is greater than the Item in the middle and then for my middle part which is greater than the Item behind my first Iterator of my array. Then I rotate those two "newly build" ranges.
According to the documentation, std::rotate does the following:
Performs a left rotation on a range of elements. Specifically, std::rotate swaps the elements in the range [first, last) in such a way that the element n_first becomes the first element of the new range and n_first - 1 becomes the last element. A precondition of this function is that [first, n_first) and [n_first, last) are valid ranges.
template< class ForwardIt >
void rotate( ForwardIt first, ForwardIt n_first, ForwardIt last );
The precondition is always fulfilled because our ranges are within the array we want to merge stuff. This will be repeated as long first is not mid and mid is not equal to last, otherwise we merged our ranges.
What follows is simply the the algo for merge sort using the above implementation of merge:
template <typename I>
void mergesort(I first, I last) {
auto&& size = std::distance(first, last);
if (size < 2) {
return;
}
auto&& mid = first + size / 2 + size % 2;
mergesort(first, mid);
mergesort(mid, last);
merge(first, mid, last);
}
