C: Сверху вниз Merge Sort - почему бесконечная рекурсия?

Question

Я пытаюсь реализовать сортировку слияния, где исходный и вспомогательный массив чередуются для каждой рекурсии. It's based on a this Java code. Описание выглядит следующим образом (Link):

Усовершенствования. Мы можем сократить время выполнения mergesort существенно с некоторыми тщательно продуманными изменениями в реализации.

[...]

• Исключите копию вспомогательного массива. Можно исключить время (но не пространство), которое требуется для копирования в вспомогательный массив, используемый для слияния. Для этого мы используем два вызова метода сортировки: один, который берет свой вход из данного массива и помещает отсортированный вывод во вспомогательный массив; другой берет свой вход из вспомогательного массива и помещает отсортированный результат в данный массив. При таком подходе, в бит рекурсивной рекурсивной обманке, мы можем организовать рекурсивные вызовы, чтобы вычисление переключает роли входного массива и вспомогательного массива на каждом уровне.

Следующий код 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, кажется, что мой код делает бесконечной рекурсии (сообщение было «может» t расти стек ").

Почему моя реализация делает бесконечную рекурсию?

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