//: mergeSort.h
/* Author: Kailash
*  Contact: http://www.ninthday.net
*/
#ifndef MERGESORT_H_
#define MERGESORT_H_
#include <iostream>
template <class Type>
class MergeSort
{
private:
    Type* m_head;
    int m_length;
protected:
    void merge(Type* array, int start, int middle, int end);
    void mergeSort(Type* array, int start, int end);
public:
    MergeSort(Type* array, int length);
    MergeSort(Type* array, int length, int start, int end);
    void show();
    Type* getHead(){
        return this->m_head; }
    int getLength(){
        return this->m_length; }
};
template <class Type>
MergeSort<Type>::MergeSort(Type* array, int length)
{
    m_head = array;
    m_length = length;
    mergeSort(array, 0, length-1);
}
template <class Type>
MergeSort<Type>::MergeSort(Type* array, int length, int start, int end)
{
    m_head = array;
    m_length = length;
    mergeSort(m_head, start-1, end-1);
}
template <class Type>
void MergeSort<Type>::merge(Type* array, int start, int middle, int end)
{
    int n1 = middle-start+1;
    int n2 = end-middle;
    int* left = new Type[n1+2];
    int* right = new Type[n2+2];
    int i, j;
    for(i=0; i<n1; i++)
        left[i] = array[start+i];
    for(j=0; j<n2; j++)
        right[j] = array[middle+j+1];
    left[n1] = 30000;
    right[n2] = 30000;
    left[n1+1] = '\0';
    right[n2+1] = '\0';
    i = j = 0;
    for(int k=start; k<=end; k++)
    {
        if(left[i]<=right[j])
        {
            array[k] = left[i];
            i += 1;
        }
        else
        {
            array[k] = right[j];
            j += 1;
        }
    }
    delete [] left;
    delete [] right;
}
template <class Type>
void MergeSort<Type>::mergeSort(Type* array, int start, int end)
{
    if(start<end)
    {
        int middle = (start+end)/2;
        mergeSort(array, start, middle);
        mergeSort(array, middle+1, end);
        merge(array, start, middle, end);
    }
}
template <class Type>
void MergeSort<Type>::show()
{
    using namespace std;
    cout <<endl;
    for(int i=0;i<m_length;i++)
        cout <<m_head[i]<<" ";
    cout <<endl;
}
#endif