c++实现合并排序算法

c++实现合并排序算法

#include <iostream>
#include <algorithm>
#include <vector>
#include <ctime>
#include <functional>
#include <string>
#include <list>

using namespace std;


template<typename type, typename comparator = std::less<type>>
struct mergesort{
public:
typename typedef std::vector<type> arraytype;
typename typedef std::vector<type>::const_iterator constitrtype;
typename typedef std::vector<type>::difference_type difftype;
private:
arraytype values;
comparator compare;

public:
mergesort(){};
mergesort(const arraytype val,const comparator& cmp = comparator())
: values(val), compare(cmp){}
mergesort(const type* begin, const type* end, const comparator& cmp = comparator())
: values(begin,end), compare(cmp) {}
arraytype doit(){ return _sortit(values.begin(), values.end()); }
private:
//helper function
arraytype _sortit(constitrtype begin, constitrtype end)const{
if(end - begin < 2) return arraytype(begin,end);
arraytype left, right;
difftype mid = (end-begin) / 2;
left = _sortit(begin, begin + mid );
right = _sortit(begin + mid , end );
return _mergesort(left,right);
}
arraytype _mergesort(const arraytype& leftarray, const arraytype& rightarray)const{
arraytype lhs(leftarray);
arraytype rhs(rightarray);
arraytype result;
while(!lhs.empty() && !rhs.empty()){
type elem = compareelem(lhs.front(),rhs.front());
if(elem == lhs.front() ) lhs.erase(lhs.begin());
else rhs.erase( rhs.begin() );
result.push_back( elem );
}
std::copy(lhs.begin(),lhs.end(), std::back_insert_iterator<arraytype>(result) );
std::copy(rhs.begin(),rhs.end(), std::back_insert_iterator<arraytype>(result) );
return result;
}
type compareelem(const type& lhs, const type& rhs)const{
return compare(lhs,rhs) ? lhs : rhs;
}
};

template<typename input>
void println(const input& in){
cout << in << endl;
}

int main(){
srand( static_cast<unsigned>(time(0)) );

const int size = 7;
int values[size] = {0};

std::generate( values, values + size, rand );
mergesort<int > msort(values,values+size);
vector<int> sorted = msort.doit();
cout <<"using std::less as comparison :\n";
std::for_each( sorted.begin(), sorted.end(),println<int>);

mergesort<int, std::greater<int> > greatersort(values,values +size);
vector<int> greatersorted = greatersort.doit();
cout << "\n\nusing std::greater as comparison : \n";
std::for_each( greatersorted.begin(), greatersorted.end(), println<int> );

return 0;
}