Merge Sort

merge_sort.cpp

#include <algorithm>
#include <iterator>
#include <vector>

template<class FI, class P, class TI>
void merge_sort_impl(FI first, FI last, P pred, TI temp)
{
	size_t size = std::distance(first, last);
	if (size == 1) {
		return;
	}

	FI mid = first;
	std::advance(mid, size / 2);
	merge_sort_impl(first, mid, pred, temp);
	merge_sort_impl(mid, last, pred, temp);

	TI temp_end = std::copy(first, mid, temp);
	TI a = temp;
	FI b = mid;
	for (FI it = first; it != last; ++it) {
		if (a == temp_end) {
			*it = *b++;
		} else if (b == last) {
			*it = *a++;
		} else if (pred(*a, *b)) {
			*it = *a++;
		} else {
			*it = *b++;
		}
	}
}

template<class FI, class P>
void merge_sort(FI first, FI last, P pred = std::less<typename std::iterator_traits<FI>::value_type>())
{
	typedef typename std::iterator_traits<FI>::value_type value_type;
	size_t size = std::distance(first, last);
	std::vector<value_type> temporary(size);

	merge_sort_impl(first, last, pred, temporary.begin());
}

template<class FI>
void merge_sort(FI first, FI last)
{
	merge_sort(first, last, std::less<typename std::iterator_traits<FI>::value_type>());
}