归并排序

void Merge(int array[] , int low , int mid , int high)
{
    int i , j , k;
    int *temp = (int *)malloc((high - low + 1)*sizeof(int));
    i = low , j = mid + 1 , k = 0;
    while(i <= mid && j <= high)
    {
        if(array[i] < array[j])        // 进行排序存入动态分配的数组中
            temp[k++] = array[i++];
        else
            temp[k++] = array[j++];
    }
    while(i <= mid)                    // 如果前一半中还有未处理完的数据，按顺序移入动态分配的数组内
        temp[k++] = array[i++];
    while(j <= high)                   // 如果前一半中还有未处理完的数据，按顺序移入动态分配的数组内
        temp[k++] = array[j++];
    for(i = low , j = 0; i<= high ; ++i)
        array[i] = temp[j++];
    free(temp);
}

void Msort(int array[] , int low , int high)
{
    int mid;
    if(low < high)
    {
        mid = (low + high)>>1;
        Msort(array , low , mid);
        Msort(array , mid + 1 , high);
        Merge(array , low , mid , high);
    }
}