C：トップダウンマージソート - なぜ無限再帰ですか？

Question

私はマージソートを実装しようとしています。ここで元の配列と補助配列はそれぞれの再帰のために交互に配置されています。 It's based on a this Java code。説明は次のようになります（Link）：

改善点。 mergesortの実行時間を大幅に削減することができます。

[...]

• 補助配列にコピーを排除します。マージに使用される補助配列にコピーするのにかかる時間（スペースではない）を削除することは可能です。そうするために、sortメソッドの2つの呼び出しを使用します.1つは、指定された配列から入力を取り出し、ソートされた出力を補助配列に入れます。もう一方は補助配列からの入力を受け取り、ソートされた出力を指定された配列に格納します。このアプローチでは、思いついた再帰トリッキーで、計算が入力配列と補助配列の役割を各レベルで切り替えるように再帰呼び出しを整理できます。

次のCコードは、2つの配列の役割を交替する私の試みです：

#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);