Merge Sort

#ifndef MERGESORT

#define MERGESORT

namespace mystd

{

template

void MergeSort(T* sortee, T* temp,

int left, int right)

{

int middle;

// Recursion base case

if (right > left)

{

middle = (left + right) / 2;

MergeSort(sortee, temp, left, middle);

MergeSort(sortee, temp, middle + 1, right);

Merge(sortee, temp, left, middle, middle + 1, right);

}

}

template

void Merge(T* sortee, T* temp,

int left, int leftEnd, int right, int rightEnd)

{

int size = rightEnd - left + 1;

int tempIndex =  left;

while(left <= leftEnd && right <= rightEnd)

{

if( *(sortee + left) < *(sortee + right) )

{

*(temp + tempIndex) = *(sortee + left);

left++;

tempIndex++;

}

else

{

*(temp + tempIndex) = *(sortee + right);

tempIndex++;

right++;

}

}

// To handle element in original

while(left <= leftEnd)

{

*(temp + tempIndex) = *(sortee + left);

left++;

tempIndex++;

}

// To handle Odd division

while(right <= rightEnd)

{

*(temp + tempIndex) = *(sortee + right);

right++;

tempIndex++;

}

for (int loop=0;loop<=size;++loop)

{

*(sortee + rightEnd) = *(temp + rightEnd);

--rightEnd;

}

}

template

void display(T*sortee, int size)

{

for (int loop=0;loop

{

cout << "Value is " << *(sortee + loop) << "\n";

}

}

}

/*

The height h of merge sort tree is O(lg n)

The overall amount or work done at 

the nodes of depth i is O(n)

We partition and merge 2i 

sequences of size n/2i

We make 2i+1 recursive calls

Thus, the total running time of merge-sort 

is O(n log n)

*/

#endif