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.

# Merge Sort Algorithm

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

mike_2000_17 2,669 21st Century Viking Team Colleague Featured Poster

mrnutty 761 Senior Poster

Rashakil Fol 978 Super Senior Demiposter Team Colleague

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.