我看过合并排序示例代码，但有一些我不明白。
void mergesort(int left, int right)
{
if (left < right)
{
int sorted[LEN];
int mid, p1, p2, idx;
mid = (left + right) / 2;
mergesort(left, mid);
mergesort(mid + 1, right);
p1 = left;
p2 = mid + 1;
idx = left;
while (p1 <= mid && p2 <= right)
{
if (arr[p1] < arr[p2])
sorted[idx++] = arr[p1++];
else
sorted[idx++] = arr[p2++];
}
while (p1 <= mid)
sorted[idx++] = arr[p1++];
while (p2 <= right)
sorted[idx++] = arr[p2++];
for (int i = left; i <= right; i++)
arr[i] = sorted[i];
}
}
在这段代码中，我不知道第三个while循环。
下面的代码将p1, p2依次插入到'sorted array'中
我想知道这个while循环是如何创建升序数组的。
如果你能详细地写下你的答案，我将不胜感激，以便我能理解。
为什么数组按升序排序
归并排序将有n个元素的数组分成n组，每组1个元素。这些单个元素运行中的每一个都可以被认为是有序的，因为它们只包含一个元素。对单个元素运行进行合并，以创建每个2个元素的排序运行。对2个元素的运行进行合并，以创建每个4个元素的排序运行。该过程将继续，直到创建一个与原始数组大小相等的排序运行。
问题中的示例是自上而下的归并排序，递归地将数组分成两半，直到达到单个元素的基本情况。在此之后，合并遵循调用链，深度先左。大多数库使用某种自底向上的归并排序(以及用于检测或创建小排序运行的插入排序)。在自下而上的归并排序中，没有递归分割，一个有n个元素的数组被视为n次运行，每次运行1个元素，并开始合并偶数和奇数运行，从左到右，在合并过程中。天花板(log2(n))通过后，数组被排序。
示例代码有一个问题，它在堆栈上为每个递归级别分配一个完整的数组，这将导致大型数组的堆栈溢出。Wiki的示例要好一些，尽管自底向上的示例应该交换引用而不是复制数组。
https://en.wikipedia.org/wiki/Merge_sort
对于问题的代码，不妨排序为全局数组，或者至少声明为静态(单个实例):
static int arr[LEN];
static int sorted[LEN];
void mergesort(int left, int right)
/* ... */
我是在该领域工作的开发人员。我很惊讶地看到你体现了归并排序。
在我们开始之前，归并排序的时间复杂度是O(nlogn)。原因可以在归并排序过程中找到!
首先，假设存在一个无序数组。
合并排序过程:
- 将其划分为数组大小为1的数组。
- 创建一个两倍于分割数组大小的数组
- 比较两个被分割的数组的元素，并将较小的元素按顺序放在创建的数组中。
- 重复此过程，直到达到原始数组的大小。
归并排序
归并排序的时间复杂度为O(nLogn)是有原因的。
在这个过程中，因为数组连续被分成两半，所以得到log的时间复杂度，因为这个过程一共执行了n次，所以得到nlogn的时间复杂度。