// Merge sort
//
// Simplified code as example for the merge sort algorithm.
//
// by feyd//godX.de
#include <vector>
#include <string>
#include <stdio.h>
// Base class, non recursive merge sort
template<class _TYPE>
class CMergeSort
{
public:
CMergeSort() {}
virtual ~CMergeSort() {}
void Sort(std::vector<_TYPE>& toSort)
{
std::vector<_TYPE> helper(toSort.size());
for(size_t nMergeSize=1; nMergeSize<toSort.size(); nMergeSize*=2)
{
size_t nSortPosition = 0;
while(nSortPosition<toSort.size())
{
size_t nLeft = nSortPosition;
size_t nRight = nSortPosition+nMergeSize;
size_t nLeftEnd = nRight;
size_t nRightEnd = nSortPosition+nMergeSize*2;
if(nLeftEnd>toSort.size())
nLeftEnd = toSort.size();
if(nRightEnd>toSort.size())
nRightEnd = toSort.size();
while(nLeft<nLeftEnd && nRight<nRightEnd)
{
if(Compare(toSort[nLeft], toSort[nRight])<=0)
{
helper[nSortPosition++] = toSort[nLeft++];
} else {
helper[nSortPosition++] = toSort[nRight++];
}
}
while(nLeft<nLeftEnd)
helper[nSortPosition++] = toSort[nLeft++];
while(nRight<nRightEnd)
helper[nSortPosition++] = toSort[nRight++];
}
for(size_t nCopy=0; nCopy<toSort.size(); nCopy++)
toSort[nCopy] = helper[nCopy];
}
}
protected:
virtual int Compare(const _TYPE& left, const _TYPE& right) = 0;
};
// Derived specialised class
class CMergeSort_String : public CMergeSort<std::string>
{
public:
CMergeSort_String() {}
virtual ~CMergeSort_String() {}
protected:
virtual int Compare(const std::string& left, const std::string& right)
{
return left.compare(right);
}
};
// Application entry point (from libc)
int main(int argc, const char* argv[])
{
printf("Mergesort test...\r\n\r\n");
{
// by std::string
printf("std::string:\r\n");
std::vector<std::string> arrayToSort;
for(int n=1; n<argc; n++)
arrayToSort.push_back(argv[n]);
CMergeSort_String sort;
sort.Sort(arrayToSort);
printf(" sorted %d elements:\r\n", (int)arrayToSort.size());
for(size_t n=0; n<arrayToSort.size(); n++)
printf(" %d. %s\r\n", (int)n+1, arrayToSort[n].c_str());
printf("\r\n");
}
}