归并排序

template 
void Sort::MergeSort(T* array, int left, int right) 
{ 
    if(left < right) 
    { 
        int mid = (left + right) / 2; 
        MergeSort(array, left, mid); 
        MergeSort(array, mid + 1, right); 
        Merge(array, left, mid, right); 
    } 
} 
//合并两个已排好序的子链 
template 
void Sort::Merge(T* array, int left, int mid, int right) 
{ 
    T* temp = new T[right - left + 1]; 
    int i = left, j = mid + 1, m = 0; 
    while(i <= mid && j <= right) 
    { 
        if(array[i] < array[j]) 
        { 
            temp[m++] = array[i++]; 
        } 
        else 
        { 
            temp[m++] = array[j++]; 
        } 
    } 
    while(i <= mid) 
    { 
        temp[m++] = array[i++]; 
    } 
    while(j <= right) 
    { 
        temp[m++] = array[j++];

    } 
    for(int n = left, m = 0; n <= right; n++, m++) 
    { 
        array[n] = temp[m]; 
    } 
    delete temp; 
}