0

Its not commented much, if any, because I thought it was self explainable. I realize that

it could have been made more flexible, but I just wasn't interested enough. Happy Coding.

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

The article starter has earned a lot of community kudos, and such articles offer a bounty for quality replies.