无法理解如何递归合并排序

Question

目前正在用Daniel Liang的C++入门自学C++。

关于合并排序的话题，我似乎无法理解他的代码是如何递归调用自己的。

我理解合并排序的一般概念，但我很难具体理解这段代码。

在本例中，我们首先将列表1,7,3,4,9,3,3,1,2及其大小（9）传递给mergeSort函数。从那里，我们将列表一分为二，直到数组大小达到1。在这种情况下，我们会得到：1,7,3,4->1,7->1。然后我们进入合并排序后半部分。在这种情况下，第二个半数组将是7。我们合并两个数组[1]和[7]，然后删除为防止内存泄漏而动态分配的两个数组。

我不明白的部分是这段代码是如何从这里运行的？delete[]firstthalf和delete[]secondhalf之后。根据我的理解，难道不应该有另一个mergeSort函数调用，以便合并排序新的firstHalf和secondhalf吗？

#include <iostream>
using namespace std;

// Function prototype
void arraycopy(int source[], int sourceStartIndex,
  int target[], int targetStartIndex, int length);

void merge(int list1[], int list1Size,
  int list2[], int list2Size, int temp[]);

// The function for sorting the numbers 
void mergeSort(int list[], int arraySize)
{
  if (arraySize > 1)
  {
    // Merge sort the first half
    int* firstHalf = new int[arraySize / 2];
    arraycopy(list, 0, firstHalf, 0, arraySize / 2);
    mergeSort(firstHalf, arraySize / 2);

    // Merge sort the second half
    int secondHalfLength = arraySize - arraySize / 2;
    int* secondHalf = new int[secondHalfLength];
    arraycopy(list, arraySize / 2, secondHalf, 0, secondHalfLength);
    mergeSort(secondHalf, secondHalfLength);

    // Merge firstHalf with secondHalf
    merge(firstHalf, arraySize / 2, secondHalf, secondHalfLength,
      list);

    delete [] firstHalf;
    delete [] secondHalf;
  }
}

void merge(int list1[], int list1Size,
  int list2[], int list2Size, int temp[])
{
  int current1 = 0; // Current index in list1
  int current2 = 0; // Current index in list2
  int current3 = 0; // Current index in temp

  while (current1 < list1Size && current2 < list2Size)
  {
    if (list1[current1] < list2[current2])
      temp[current3++] = list1[current1++];
    else
      temp[current3++] = list2[current2++];
  }

  while (current1 < list1Size)
    temp[current3++] = list1[current1++];

  while (current2 < list2Size)
    temp[current3++] = list2[current2++];
}

void arraycopy(int source[], int sourceStartIndex,
  int target[], int targetStartIndex, int length)
{
  for (int i = 0; i < length; i++)
  {
    target[i + targetStartIndex] = source[i + sourceStartIndex];
  }
}

int main()
{
  const int SIZE = 9;
  int list[] = {1, 7, 3, 4, 9, 3, 3, 1, 2};
  mergeSort(list, SIZE);
  for (int i = 0; i < SIZE; i++)
    cout << list[i] << " ";

  return 0;
}  

Answer 1

根据我的理解，难道不应该有另一个mergeSort函数调用，以便合并排序新的firstHalf和secondhalf吗？

它是在递归调用期间隐式发生的。当你到达这两条线时：

delete [] firstHalf;
delete [] secondHalf;

这意味着对mergeSort的一次调用已完成。如果此调用属于合并前半部分，则代码从后面的行开始，即这些行：

// Merge sort the second half
int secondHalfLength = arraySize - arraySize / 2;
...

但是，如果该调用属于后半部分的合并，则控制返回到紧随该调用之后的行，即这些行：

// Merge firstHalf with secondHalf
merge(firstHalf, arraySize / 2, secondHalf, secondHalfLength,
  list);

如果一切都按计划进行的话。