Unoptimized single-function versions of merge-sort.

merge-sort-single-function.hpp

#ifndef MERGE_SORT_SINGLE_FUNCTION_HPP
#define MERGE_SORT_SINGLE_FUNCTION_HPP

#include <assert.h>
#include <algorithm>
#include <iterator>
#include <vector>

template<typename Iterator,
		 typename T = typename std::iterator_traits<Iterator>::value_type>
void merge_sort(Iterator begin, Iterator end)
{
	auto distance = std::distance(begin, end);
	
	if (distance < 2) return;

	distance /= 2;
	
	auto middle = begin;
	
	std::advance(middle, distance);
	
	merge_sort(begin, middle);
	merge_sort(middle, end);
	
	if (*middle < *std::prev(middle))
	{
		std::vector<T> auxiliary(begin, end);
		
		auto i = auxiliary.begin();
		auto j = auxiliary.begin();
		
		std::advance(j, distance);
		
		auto stop = j;
		auto aux_end = auxiliary.end();
		
		for ( ; begin != end; ++begin)
		{
			if ((j == aux_end) || (i != stop && *i <= *j))
			{
				*begin = *i++;
			}
			
			else *begin = *j++;
		}
	}
}

template<typename Sequence, typename T = typename Sequence::value_type>
void merge_sort(Sequence& sequence, std::size_t begin, std::size_t end)
{
	auto size = end - begin;
	
	if (size < 2) return;
	
	auto middle = begin + size/2;
	
	merge_sort(sequence, begin, middle);
	merge_sort(sequence, middle, end);
	
	if (sequence[middle] < sequence[middle - 1])
	{
		std::vector<T> auxiliary(std::begin(sequence), std::end(sequence));
		
		for (auto i = begin, j = middle; begin < end; ++begin)
		{
			if ((j == end) || (i < middle && auxiliary[i] <= auxiliary[j]))
			{
				sequence[begin] = auxiliary[i++];
			}
			
			else sequence[begin] = auxiliary[j++];
		}
	}
}

#endif /* MERGE_SORT_SINGLE_FUNCTION_HPP */