C：自顶向下合并排序-为什么是无限递归？

Question

我正在尝试实现合并排序，其中原始数组和辅助数组为每个递归交替。它基于Java代码。描述如下（链接）：

改进。通过对实现进行一些经过仔细考虑的修改，我们可以大幅缩短mergesort的运行时间。

[...]

• 消除到辅助阵列的副本。可以消除复制到用于合并的辅助阵列所需的时间（但不是空间）。为此，我们使用了两个sort方法调用，一个调用从给定数组中获取其输入，并将排序后的输出放入辅助数组中；另一个从辅助数组获取输入，并将排序后的输出放入给定数组。通过这种方法，我们可以使用一种令人费解的递归技巧，安排递归调用，以便计算在每个级别切换输入数组和辅助数组的角色

下面的C代码是我尝试交替两个数组的角色的代码：

#include <stdlib.h>
#include <string.h>

#include "mergesort.h"

#define THRESHOLD 20

static size_t size_m = 0;
static size_t elements = 0;
static size_t mod = 0;
static char *a = NULL;
static char *b = NULL;
static char *i = NULL;
static char *j = NULL;
static char *k = NULL;
static char *start = NULL;
static char *middle = NULL;
static char *end = NULL;
static char *e = NULL;
static int (*cmp_m)(const void *, const void *) = NULL;

void sort(char *a, char *b, size_t lmod, size_t rmod) {
    elements = rmod-lmod+1;

    //========== INSERTION SORT ==========
    if(elements <= THRESHOLD) {
        start = b+size_m*lmod;
        end = b+size_m*rmod;

        for(i = start; i <= end; i += size_m) {

            memcpy(e, i, size_m);
            for(j = i-size_m; j >= start && (*cmp_m)((void *)e, (void *)j) < 0; j -= size_m) {
                memcpy(j+size_m, j, size_m);
            }
            memcpy(j+size_m, e, size_m);
        }

        return;
    }

    //========== SPLIT OPERATION ==========//
    size_t mmod = (rmod-lmod)/2;

    sort(b, a, lmod, mmod);
    sort(b, a, mmod+1, rmod);

    //========== CHECK IF CURRENT SUBARRAY IS ALREADY SORTED ==========//
    if((*cmp_m)((void *)(a+size_m*mmod), (void *)(a+size_m*(mmod+1))) <= 0) {
        memcpy(b+lmod, a+lmod, size_m*elements);
        return;
    }

    //========== MERGE OPERATION ==========//
    start = a+size_m*lmod;
    middle = a+size_m*mmod;
    end = a+size_m*rmod;

    i = start;
    j = middle+size_m;

    for(k = start; k <= end; k += size_m) {
        mod = k-a;

        if(i <= middle && (j > end || (*cmp_m)((void *)i, (void *)j) <= 0)) {
            memcpy(b+mod, i, size_m);
            i += size_m;
        } else {
            memcpy(b+mod, j, size_m);
            j += size_m;
        }
    }
}

void mergesort(void *array, size_t num, size_t size, int (*cmp)(const void *a, const void *b)) {
    size_m = size;
    threshold = THRESHOLD;
    a = (char *)array;
    b = (char *)malloc(num*size_m);
    e = (char *)malloc(size_m);
    cmp_m = cmp;

    memcpy(b, a, size_m*num);
    sort(b, a, 0, num-1);

    free(b);
    free(e);
}

在使用valgrind进行分析后，我的代码似乎进行了无限递归（消息是“不能增长堆栈”）。

为什么我的实现做无限递归？

Answer 1

也许valgrind不能通过递归判断元素是否减少
试试下面的代码。

static void sort(char *a, char *b, size_t n) {
        :
        :
    //========== SPLIT OPERATION ==========//

    size_t  m = n/2;
    sort(b, a, m);
    sort(b + m * size_m, a + m * size_m, n - m);