[ create a new paste ] login | about

Link: http://codepad.org/bFbD6hQy    [ raw code | output | fork ]

ninwa - C++, pasted on Mar 20:
#include <algorithm>
#include <iostream>
#include <vector>

template <typename RandomAccessIterator>
void mergesort(RandomAccessIterator begin, RandomAccessIterator end)
{
	double half_distance = floor((end-begin)/2);
	RandomAccessIterator half_iter = begin + static_cast<typename RandomAccessIterator::difference_type>(half_distance);

	if(begin == end)
		return;

	if(begin+1 == end)
		return;

	if(begin+2 == end)
	{
		if(*(begin) > *(begin+1))
		{
			typename RandomAccessIterator::value_type t = *(begin);
			*(begin) = *(begin+1);
			*(begin+1) = t;
		}
		return;
	}

	RandomAccessIterator left  = begin;
	RandomAccessIterator right = half_iter;

	mergesort(left, right+1);
	mergesort(right, end);

	while(left != half_iter + 1 && right != end)
	{
		if(*(left) > *(right))
		{
			typename RandomAccessIterator::value_type t = *(left);
			*(left) = *(right);
			*(right) = t;
			--left;
			++right;
		}  
		else
		{
			++left;
		}
	}
}

int main(int argc, char* argv[])
{
	std::vector<int> v;
	v.push_back(0);
	v.push_back(7);
	v.push_back(1);
	v.push_back(5);
	v.push_back(9);
	v.push_back(3);
	v.push_back(3);
	v.push_back(5);
	v.push_back(9);
	v.push_back(3);
	v.push_back(3);
	v.push_back(5);
	v.push_back(9);
	v.push_back(3);
	v.push_back(3);

	mergesort(v.begin(), v.end());

	for( vector<int>::iterator i = v.begin();
             i != v.end();
             ++i ) {
            std::cout << *i << " ";
        }
}


Output:
1
0 1 3 3 3 3 3 3 7 5 5 5 9 9 9 


Create a new paste based on this one


Comments: