请问第二个函数有什么作用

Question

请问第二个函数有什么作用？
void Merge(int* input, int low, int mid, int high) //第一个函数
{

int* tmp = new int[high-low+1];

int i = low;

int j = mid + 1;

int k = 0;

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

{

if(input[i] <= input[j])

{

tmp[k++] = input[i++];

}

else

{

tmp[k++] = input[j++];

}

}

while(i <= mid)

tmp[k++] = input[i++];

while(j <= high)

tmp[k++] = input[j++];

i = low;

j = 0;

while(j < k)

input[i++] = tmp[j++];

delete[] tmp;

}

void MergeSort(int* input, int first, int last)//第二个函数

{

int mid = 0;

if(first < last)

{

mid = (first + last) / 2;

MergeSort(input, first, mid);

MergeSort(input, mid+1, last);

Merge(input, first, mid, last);

}

}

Answer 1

这两个函数实现的是归并排序，归并排序的思路是每次将数组分割为前后两部分，然后将两部分排序后合并起来，这个过程递归进行，最后回溯，实现对整个数组的排序，第一个函数实现的是将数组的前后两部分进行排序，而第二个函数实现的是控制递归和回溯过程