mergesort.cpp

// 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");
    }
}