在合并排序算法中合并
我知道合并排序算法的基本概念，但是通过递归实现它时，我很难理解它是如何工作的。 根据我的理解，合并排序函数将我们当前的数组分割成两半，并使用递归我们继续这样做直到我们为每一边留下1个元素。
如果我们的数组是{38,27,43,3,9,82,10}，那么我们的递归将通过使用子阵列（原始数组的左侧）调用它自己开始，并且每次重复该过程，将数组减半并存储最左边直到我们达到1个元素：
38 27 43 3 9 82 10
38 27 43 3 <-split
<---first subroutine/recursion
38 27 <-split
<---second subroutine/recursion
38 <---only 1 element left so we return the value back to the first subroutine that called
然后在我们的第二个子程序中，我们转到下一行：right = merge_sort（right），它再次调用它自己来分割子数组并存储最右边：
38 27 <-split
<---second subroutine/recursion
27
<---only 1 element left so we return the value back to the first subroutine that called
然后在第二个子例程中，我们转到下一行：result = merge（left，right），它调用merge函数对我们的左和右数组进行排序，这些数组只是38和27.合并函数根据这两个值进行排序更小，然后它将第一个添加到数组， 虽然我不确定哪个数组。 （我需要对此进行说明;每当我们合并两个先前的数组时，我们是不是应该有一个新的数组？）然后，merge函数从合并函数返回“结果”给另一个结果变量。 我假设这个结果是38和27顺序排列的新数组。 然后它看起来像我们再次将该结果返回到所谓的合并排序函数，但我很困惑，因为这不会结束一切 ？ 第一个暂停左侧递归的子程序怎么样？ 我不确定会发生什么情况：
38 27 43 3
43 3
43
and
43 3
3
伪代码：
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
在编写merge_sort函数之后，需要合并上面创建的左列表和右列表。 merge（）函数有几个变体; 一种可能性是：
function merge(left,right)
var list result
while length(left) > 0 or length(right) > 0
if 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)
else if length(left) > 0
append first(left) to result
left = rest(left)
else if length(right) > 0
append first(right) to result
right = rest(right)
end while
return result
http://www.princeton.edu/~achaney/tmve/wiki100k/docs/Merge_sort.html
我不知道它是否是你要找的是什么，但你可以通过更换简化合并循环or与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() ，其中一个参数为'tag'（用于标识正在使用哪个调用）以及其他参数要打印的数据结构。 对于生产质量代码，我的诊断打印函数也会采用FILE *fp参数并写入给定文件; 我在这里欺骗并使用stdout 。 额外的通用性意味着该函数可用于写入stderr或日志文件以及stdout ，或替代stdout 。
空间管理
merge_sort()代码将完整的输入数组复制为两个较小的数组（ left和right ），然后对较小的数组进行排序（递归），并将已排序的较小数组合并到输入数组中。 这发生在递归的每个日志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("-->> %sn", func);
}
static void exit_func(const char *func)
{
printf("<<-- %sn", 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