Merge sort.cpp

From Algorithmist
Jump to: navigation, search

This is an implementation of Merge sort in C++.

namespace merge_sort
{
 
template< 
	typename difference_type, 
	typename const_iterator_type, 
	typename iterator_type, 
	typename order_type, 
	typename swapper_type >
merge( 
	difference_type const size0, 
	const_iterator_type const begin0, 
	difference_type const size1, 
	const_iterator_type const begin1, 
	iterator_type const target_begin, 
	order_type const order, 
	swapper_type const swapper )
{
	iterator_type target( target_begin );
	difference_type rest0(size0);
	iterator_type current0(begin0);
	difference_type rest1(size1);
	iterator_type current1(begin1);
	difference_type rest_size;
	iterator_type rest_current;
	while( true ) {
		if(rest0!=0) {
			if(rest1!=0) {
				if( order( current0, current1 ) ) {
					swapper( target, current0 );
					++current0;
					--rest0;
				} else {
					swapper( target, current1 );
					++current1;
					--rest1;
				}
				++target;
			} else {
				rest_current = current0;
				rest_size = rest0;
				break;
			}
		} else {
			rest_current = current1;
			rest_size = rest1;
			break;
		}
	}
	while( rest_size != 0 ) {
		swapper( target, rest_current );
		++target;
		++rest_current;
		--rest_size;
	}
}
 
 
template< typename difference_type, typename iterator_type, typename order_type, typename swapper_type >
sort_recursive( difference_type size, iterator_type begin0, iterator_type begin1, bool target, order_type order, swapper_type swapper )
{
	if( size > 1 ) {
		difference_type const first_part_size( size / 2 );
		difference_type const second_part_size( size - first_part_size );
		bool const internal_target( !target );
		sort_recursive( first_part_size, begin0, begin1, internal_target, order, swapper );
		sort_recursive( second_part_size, begin0+first_part_size, begin1+first_part_size, internal_target, order, swapper );
		if( target ) {
			merge( first_part_size, begin0, second_part_size, begin0+first_part_size, begin1, order, swapper );
		} else {
			merge( first_part_size, begin1, second_part_size, begin1+first_part_size, begin0, order, swapper );
		}
	} else if( size == 1 ) {
		if( target ) {
			swapper( begin0, begin1 );
		}
	}
}
 
template< typename difference_type, typename iterator_type, typename order_type, typename swapper_type >
sort( difference_type size, iterator_type begin, iterator_type temp_begin, order_type order, swapper_type swapper )
{
	sort_recursive( size, begin, temp_begin, false, order, swapper );
}
 
}
 
/* Example of usage: */
#include <cstdio>
#include <cstdlib>
#include <vector>
 
bool order( int const* i1, int const* i2 )
{
	return( (*i1) < (*i2) );
}
 
void swapper( int* i1, int* i2 )
{
	std::swap( *i1, *i2 );
}
 
int main()
{
	int const n( 100 );
	int a[100];
	for (int i = 0; i < n; i++) a[i] = rand();
	int temp[100];
	merge_sort::sort( n, a, temp, &order, &swapper );
	for (int i = 0; i < n; i++) printf("%d\n", a[i]);
	return 0;
}