合并排序算法中的合并

Question

我知道合并排序算法的基本概念，但是当涉及到通过递归实现它时，我很难理解它是如何工作的。据我所知，合并排序函数将我们当前的数组分成两半，并使用递归我们一直这样做，直到每边只剩下一个元素。

如果我们的数组是{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函数根据较小的值对两个值进行排序，然后将第一个值添加到数组中，尽管我不确定是哪个数组。（我需要这方面的说明；我们不是应该每次合并前两个数组时都有一个新的数组吗？）然后，merge函数将“result”从调用merge函数返回到merge排序函数中的另一个结果变量。我假设这个结果是按顺序排序的38和27的新数组。然后，看起来我们再次将结果返回给被称为merge-sort函数的函数，但我感到困惑，因为这不会结束一切吗？为左侧递归暂停的第一个子例程如何？我不确定会发生什么：

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\u 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\u sort.html

Answer 1

我不确定这是否是您想要的，但您可以通过在主条件中用和替换或来简化合并循环：

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可变长度数组（C11中的可选特性）。如果使用DDEBUG编译，则在程序运行时会得到广泛的跟踪。如果没有进行编译，则只打印输入（未排序）和输出（排序）数组。我需要它来诊断一个愚蠢的打字错误（一个明显需要l的r位置）。注意一般技术：

1. 文档输入和退出功能
2. 创建一个诊断打印函数（此处为dump_array（），其中一个参数为“tag”（用于识别正在使用的调用），另一个参数为要打印的数据结构
3. 在适当的时候调用诊断打印功能
4. 使启用或禁用诊断变得容易

对于生产质量代码，我的诊断打印函数还采用一个FILE*fp参数并写入给定文件；我在这里作弊并使用stdout。额外的通用性意味着该函数可以用于写入stderr或日志文件，或者代替stdout。

代码将完整的输入数组复制到两个较小的数组中（left和right），然后对较小的数组进行排序（递归），并将排序后的较小数组合并到输入数组中。这发生在递归的每一个log N级别。一些实证测试表明，使用的空间约为2N个项目-这是O（N）空间使用。

我们不是应该每次合并前两个数组时都有一个新数组吗？

在函数式编程语言中，您会有新的数组。在C中，您也使用输入数组作为输出数组。代码将原始输入数组复制到单独的较小数组中，对这些较小的数组进行排序，并将排序后的较小数组合并到原始数组中。

我的另一个问题是，代码中的哪个过程允许我们回到递归之前，在递归之前我们分割数组的左侧，这样我们可以在右侧得到43个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