分治：合并排序

void Merge(int *array, int low, int middle, int high)  //合并
{
    int *A = new int[high - low + 1];  
    int i = low;
    int j = middle + 1;
    int k = 0;
    while(i <= middle && j <= high) 
    {
        if(array[i] < array[j])  
            A[k++] = array[i++];
        else           A[k++] = array[j++];
    }
    while(i <= middle)         A[k++] = array[i++];
    while(j <= high)          A[k++] = array[j++];
    for(i = low; i <= high; i++)  
        array[i] = A[i - low];
}
void MergeSort(int *array, int low, int high)
{
    int middle;  //二分
    if(low < high)
    {
        middle = (low + high) / 2;  //二分
        MergeSort(array, low, middle); //前半部
        MergeSort(array, middle + 1, high);  //后半部
        Merge(array, low, middle, high);  //合并
    }
}