#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 << " ";
}
}