求逆序数 (二)

int
merge(int *numbers, int begin, int middle, int end)
{
int n1 = middle - begin + 1;
int n2 = end - middle;
int* numbers1 = (int*)malloc((n1 + 1) * sizeof(int));
int* numbers2 = (int*)malloc((n2 + 1) * sizeof(int));
int i,
j,
k;

for(i = 0; i < n1; i++)
numbers1[i] = numbers[begin + i];
numbers1[i] = MAX;
for(i = 0; i < n2; i++)
numbers2[i] = numbers[middle + i + 1];
numbers2[i] = MAX;

i = 0;
j = 0;
for(k = begin; k < end + 1; k++)
{
if(numbers1[i] < numbers2[j])
{
numbers[k] = numbers1[i];
i++;
continue;
}
else
{
numbers[k] = numbers2[j];
j++;
if(i < n1)
{
totalCount += (middle - begin + 1 - i);
}
continue;
}
}

free(numbers1);
free(numbers2);

return 0;
}三、后续工作
这里有给出了一个运用分治算法思想解决问题的例子。在后续的博客中还会给出其他一些应用分治思想解决问题的例子。