sort.h

#ifndef __SEAL_SORT_H__
#define __SEAL_SORT_H__

#include "randaccess.h"
#include "utils.h"

namespace seal
{

enum SortOrder
{
    ASCENDING      = 0,

    DESCENDING     = 1
};

template <typename T>
class SortingAlgorithm
{
public:

    SortingAlgorithm(void) {}

    virtual ~SortingAlgorithm() {}

    virtual void operator()(RandomAccess<T> &array, int from, int to, SortOrder order = ASCENDING) {}

    virtual void sort(RandomAccess<T> &array, int from, int to, SortOrder order = ASCENDING) = 0;

}; // class SortingAlgorithm

// *******************************************************************************
// *******************************************************************************
// *******************************************************************************

template <typename T>
class BubbleSort : public SortingAlgorithm<T>
{
public:
    BubbleSort(void) : SortingAlgorithm<T>() {}

    virtual ~BubbleSort() {}

    virtual void operator()(RandomAccess<T> &array, int from, int to, SortOrder order = ASCENDING);

    virtual void sort(RandomAccess<T> &array, int from, int to, SortOrder order = ASCENDING) 
    {
        operator()(array, from, to, order);
    }

}; // class BubbleSort

template <typename T>
void BubbleSort<T>::operator()(RandomAccess<T> &a, int from, int to, SortOrder order)
{
    if (to < from)
    {
        order = (order == ASCENDING ? DESCENDING : ASCENDING);
        swap(from, to);
    }
        
    if (order == ASCENDING)
    {
        for (int n = to; n > from; n--)
        {
            for (int i = from; i < n; i++)
            {
                if (a[i] > a[i+1])
                {
                    T temp = a[i];
                    a[i] = a[i+1];
                    a[i+1] = temp;
                }
            }
        }
    }

    if (order == DESCENDING)
    {
        for (int n = to; n > from; n--)
        {
            for (int i = from; i < n; i++)
            {
                if (a[i] < a[i+1])
                {
                    T temp = a[i];
                    a[i] = a[i+1];
                    a[i+1] = temp;
                }
            }
        }
    }

} // BubbleSort::operator()

// *******************************************************************************
// *******************************************************************************
// *******************************************************************************

template <typename T>
class MergeSort : public SortingAlgorithm<T>
{
public:
    
    MergeSort(void) : SortingAlgorithm<T>() {}

    virtual ~MergeSort() {}

    virtual void operator()(RandomAccess<T> &array, int from, int to, SortOrder order = ASCENDING);

    virtual void sort(RandomAccess<T> &array, int from, int to, SortOrder order = ASCENDING)
    {
        operator()(array, from, to, order);
    }

}; // class MergeSort

template <typename T>
void MergeSort<T>::operator()(RandomAccess<T> &a, int from, int to, SortOrder order)
{
    if (to < from)
    {
        order = (order == ASCENDING ? DESCENDING : ASCENDING);
        swap(from, to);
    }

    if (to == from)
        return;
    else
    {
        int mid = (to+from)/2;
        operator()(a, from, mid, order);
        operator()(a, mid+1, to, order);
        
        // Merge the two halves.
        int insertPos = from;
        if (order == ASCENDING)
        {
            for (int i = mid+1; i <= to; i++)
            {
                for (int j = insertPos; j < i; j++)
                {
                    if (a[j] > a[i])
                    {
                        T temp = a[i];
                        for (int k = i; k > j; k--)
                            a[k] = a[k-1];
                     
                        a[j] = temp;
                        insertPos = j;
                        break;
                    }
                }
            }
        }

        if (order == DESCENDING)
        {
            for (int i = mid+1; i <= to; i++)
            {
                for (int j = insertPos; j < i; j++)
                {
                    if (a[j] < a[i])
                    {
                        T temp = a[i];
                        for (int k = i; k > j; k--)
                            a[k] = a[k-1];
                     
                        a[j] = temp;
                        insertPos = j;
                        break;
                    }
                }
            }
        }
    }
}

// *******************************************************************************
// *******************************************************************************
// *******************************************************************************

} // End of namespace seal

#endif // __SEAL_SORT_H__

---