我不确定它是否是您要查找的内容，但是您可以通过替换主要条件中的orwith来简化合并循环：and
while length(left) > 0 and length(right) > 0
if first(left) ≤ first(right)
append first(left) to result
left = rest(left)
else
append first(right) to result
right = rest(right)
end while
# You know that one of left and right is empty
# Copy the rest of the data from the other
while length(left) > 0
append first(left) to result
left = rest(left)
end while
while length(right) > 0
append first(right) to result
right = rest(right)
end while
是的，有三个循环，但最后两个循环中只有一个被执行过。
基于伪代码的工作 C99 代码
因此代码使用 C99 可变长度数组（C11 中的一个可选功能）。如果使用 编译-DDEBUG，您将在程序运行时获得广泛的跟踪。如果没有编译，您只会打印输入（未排序）和输出（排序）数组。我需要它来诊断一个愚蠢的错字（显然需要r_pos一个）。l_pos注意一般技术：
- 文档进入和退出函数
- 创建一个诊断打印函数（这里
dump_array()有一个参数是“标签”（用于识别正在使用的调用），另一个参数是要打印的数据结构。
- 在合适的位置调用诊断打印功能。
- 使启用或禁用诊断变得容易。
对于生产质量代码，我的诊断打印函数也接受一个FILE *fp参数并写入给定文件；我作弊并stdout在这里使用。额外的通用性意味着该函数可用于写入stderr或写入日志文件，以及，或代替，stdout。
空间管理
代码将merge_sort()完整的输入数组复制到两个较小的数组（left和right）中，然后对较小的数组进行排序（递归）并将排序后的较小数组合并到输入数组中。这发生在每个 log N 递归级别。一些经验测试表明，使用的空间大约是 2N 个项目——它是 O(N) 的空间使用量。
每次合并两个先前的数组时，我们不应该有一个新数组吗？
在函数式编程语言中，您将拥有新的数组。在 C 中，您也可以使用输入数组作为输出数组。该代码将原始输入数组复制到单独的较小数组中，对这些较小数组进行排序，并将排序后的较小数组合并到原始数组中。
我的另一个问题是代码中的哪个过程允许我们回到递归之前，我们拆分数组的左侧，这样我们就可以在右侧工作以获得 43 a 3 以便也合并它们。
拆分过程会创建输入数组的副本（因此原始数据中的信息暂时是多余的）。合并过程将（现在已排序的）拆分数组复制回原始数组。（主要是重复我自己。）
来源
#include <stddef.h>
extern void merge_sort(int *array, size_t arrlen);
/* Debug */
#ifdef DEBUG
static void dump_array(const char *tag, int *array, size_t len);
static void enter_func(const char *func);
static void exit_func(const char *func);
#else
#define dump_array(t, a, l) ((void)0)
#define enter_func(f) ((void)0)
#define exit_func(f) ((void)0)
#endif
/*
function merge(left, right)
var list result
while length(left) > 0 and length(right) > 0
if first(left) ≤ first(right)
append first(left) to result
left = rest(left)
else
append first(right) to result
right = rest(right)
end while
# You know that one of left and right is empty
# Copy the rest of the data from the other
while length(left) > 0
append first(left) to result
left = rest(left)
end while
while length(right) > 0
append first(right) to result
right = rest(right)
end while
return result
end function
*/
static void merge(int *left, size_t l_len, int *right, size_t r_len, int *output)
{
size_t r_pos = 0;
size_t l_pos = 0;
size_t o_pos = 0;
enter_func(__func__);
dump_array("Left:", left, l_len);
dump_array("Right:", right, r_len);
while (r_pos < r_len && l_pos < l_len)
{
if (right[r_pos] < left[l_pos])
output[o_pos++] = right[r_pos++];
else
output[o_pos++] = left[l_pos++];
}
while (r_pos < r_len)
output[o_pos++] = right[r_pos++];
while (l_pos < l_len)
output[o_pos++] = left[l_pos++];
dump_array("Output:", output, r_len + l_len);
exit_func(__func__);
}
/*
function merge_sort(m)
if length(m) ≤ 1
return m
var list left, right, result
var integer middle = length(m) / 2
for each x in m up to middle
add x to left
for each x in m after middle
add x to right
left = merge_sort(left)
right = merge_sort(right)
result = merge(left, right)
return result
*/
void merge_sort(int *array, size_t len)
{
if (len <= 1)
return;
int left[(len+1)/2];
int l_pos = 0;
int right[(len+1)/2];
int r_pos = 0;
size_t mid = len / 2;
enter_func(__func__);
dump_array("Input:", array, len);
for (size_t i = 0; i < mid; i++)
left[l_pos++] = array[i];
for (size_t i = mid; i < len; i++)
right[r_pos++] = array[i];
dump_array("Left:", left, l_pos);
dump_array("Right:", right, r_pos);
merge_sort(left, l_pos);
merge_sort(right, r_pos);
merge(left, l_pos, right, r_pos, array);
dump_array("Result:", array, len);
exit_func(__func__);
}
/* Test code */
#include <stdio.h>
#ifdef DEBUG
static void enter_func(const char *func)
{
printf("-->> %s\n", func);
}
static void exit_func(const char *func)
{
printf("<<-- %s\n", func);
}
#endif
/* dump_array is always used */
#undef dump_array
static void dump_array(const char *tag, int *array, size_t len)
{
printf("%-8s", tag);
for (size_t i = 0; i < len; i++)
printf(" %2d", array[i]);
putchar('\n');
}
int main(void)
{
int array[] = { 38, 27, 43, 3, 9, 82, 10 };
size_t arrlen = sizeof(array) / sizeof(array[0]);
dump_array("Before:", array, arrlen);
merge_sort(array, arrlen);
dump_array("After:", array, arrlen);
return 0;
}
样本输出
非调试
Before: 38 27 43 3 9 82 10
After: 3 9 10 27 38 43 82
调试
Before: 38 27 43 3 9 82 10
-->> merge_sort
Input: 38 27 43 3 9 82 10
Left: 38 27 43
Right: 3 9 82 10
-->> merge_sort
Input: 38 27 43
Left: 38
Right: 27 43
-->> merge_sort
Input: 27 43
Left: 27
Right: 43
-->> merge
Left: 27
Right: 43
Output: 27 43
<<-- merge
Result: 27 43
<<-- merge_sort
-->> merge
Left: 38
Right: 27 43
Output: 27 38 43
<<-- merge
Result: 27 38 43
<<-- merge_sort
-->> merge_sort
Input: 3 9 82 10
Left: 3 9
Right: 82 10
-->> merge_sort
Input: 3 9
Left: 3
Right: 9
-->> merge
Left: 3
Right: 9
Output: 3 9
<<-- merge
Result: 3 9
<<-- merge_sort
-->> merge_sort
Input: 82 10
Left: 82
Right: 10
-->> merge
Left: 82
Right: 10
Output: 10 82
<<-- merge
Result: 10 82
<<-- merge_sort
-->> merge
Left: 3 9
Right: 10 82
Output: 3 9 10 82
<<-- merge
Result: 3 9 10 82
<<-- merge_sort
-->> merge
Left: 27 38 43
Right: 3 9 10 82
Output: 3 9 10 27 38 43 82
<<-- merge
Result: 3 9 10 27 38 43 82
<<-- merge_sort
After: 3 9 10 27 38 43 82