/*

归并排序

算法思想：归并排序法是将两个（或两个以上）有序表合并成一个新的有序表，

即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

*/

template <typename T>

void Merge(T *array,int low,int mid,int high)

{

int i = low;

int j = mid + 1;

int p = 0;

T *temp;

temp = (ElemType *)malloc((high-low+1)*sizeof(ElemType));

if(!temp)

return;

while(i <= mid && j <= high) {

temp[p++] = (array[i] <= array[j]) ? array[i++] : array[j++];

}

while(i <= mid)

temp[p++] = array[i++];

while(j <= high)

temp[p++] = array[j++];

for(p=0, i=low; i <= high; p++,i++) {

array[i] = temp[p];

}

free(temp); //及时释放

}

void MergeSort(T array[], int low, int high)

{

if (low < high)

{

int mid = low + (high - low) / 2; //均分

MergeSort(array, low, mid); //对前半部分

MergeSort(array, mid+1, high);

Merge(array, low, mid, high);

}

}