Its a typical implementation of mergesort algorithm. It runs in a stable time of O(n*log(n) ). Just thought, I would add it to the library. Its been tested, although not very throughly, so if any bugs are found, just post it here, so others can be aware of them.

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.

## firstPerson 761

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