Обнаружение кучи - реализация mergesort со строками

Question

Ранее я сделал свою собственную реализацию «классического» объединения, которое отсортировало массив int. Следуйте код:

#include <stdio.h> 
#include <stdlib.h> 

void merge(int a[], int b[], int c[], int m, int n) 
{ 
    int i = 0, j = 0, k = 0; 

    while (i < m && j < n) 
     if (a[i] < b[j]) 
      c[k++] = a[i++]; 
     else 
      c[k++] = b[j++]; 
    while (i < m) 
     c[k++] = a[i++]; 
    while (j < n) 
     c[k++] = b[j++]; 
} 

void mergesort_pot2(int key[], int n) 
{ 
    int j, k, *w; 

    w = calloc(n, sizeof(int)); 
    for (k = 1; k < n; k *= 2) { 
     for (j = 0; j < n - k; j += 2 * k) 
      merge(key + j, key + j + k, w + j, k, k); 
     for (j = 0; j < n; ++j) 
      key[j] = w[j]; 
    } 
    free(w); 
} 

void mergesort(int key[], int n) 
{ 
    int i, cnt = 0, *x, v, b = 0, vv = 0, bb; 

    while (n - cnt > 0) 
    { 
     for (i = 1; i < n - cnt; i *= 2); 
     if (i > n - cnt) 
      i /= 2; 

     x = calloc(i, sizeof(int));      

     v = 0; 
     while (v < i) 
      x[v++] = key[b++]; 

     mergesort_pot2(x, i);       

     bb = 0; 
     while (bb < i)         
      key[vv++] = x[bb++]; 

     free(x);           
     cnt += i;          
    } 
} 

int main(void) 
{ 
    int i, key[] = { 4, 3, 1, 67, 55, 8, 0, 4, 
     -5, 37, 7, 4, 2, 9, 1, -1, 100}; 

    printf("Before mergesort:\n"); 
    for (i = 0; i < 17; ++i) 
     printf("%4d", key[i]); 
    putchar('\n'); 

    mergesort(key, 17); 

    printf("After mergesort:\n"); 
    for (i = 0; i < 17; ++i) 
     printf("%4d", key[i]); 
    putchar('\n'); 
    return 0; 
} 

Теперь, как упражнение, я адаптировать этот код, чтобы сделать его работы с массивом полукокса *, но у меня есть кучи ошибок где-нибудь. Я попытался отладить его с помощью Dr. Memory, но он разогнал мою визуальную студию 2013 без работы, но это еще одна история.

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

#define LENGTH  5 

void merge(char *a[], char *b[], char *c[], int m, int n) 
{ 
    int i = 0, j = 0, k = 0; 

    while (i < m && j < n) 
     if (strcmp(a[i], b[j]) < 0) 
      c[k++] = a[i++]; 
     else 
      c[k++] = b[j++]; 
    while (i < m) 
     c[k++] = a[i++]; 
    while (j < n) 
     c[k++] = b[j++]; 
} 

void mergesort_pot2(char *key[], int n) 
{ 
    int j, k; 
    char **w; 
    int i; 

    w = calloc(n, sizeof(char *)); 
    for (i = 0; i < n; ++i) 
     w[i] = calloc(strlen(key[i]), sizeof(char)); 

    for (k = 1; k < n; k *= 2) { 
     for (j = 0; j < n - k; j += 2 * k) 
      merge(key + j, key + j + k, w + j, k, k); 
     for (j = 0; j < n; ++j) 
      key[j] = w[j]; 
    } 
    for (i = 0; i < n; ++i) 
     free(w[i]); 
    free(w); 
} 

void mergesort(char *key[], int n) 
{ 
    int i, cnt = 0, v, b = 0, vv = 0, bb; 
    char **x; 
    int y; 

    while (n - cnt > 0) 
    { 
     for (i = 1; i < n - cnt; i *= 2); 
     if (i > n - cnt) 
      i /= 2; 

     x = calloc(i, sizeof(char *)); 

     for (y = 0; y < i; ++y) 
      x[y] = calloc(strlen(key[y]), sizeof(char));      
     v = 0; 
     while (v < i) 
      strcpy(x[v++], key[b++]); 

     mergesort_pot2(x, i);       

     bb = 0; 
     while (bb < i)         
      strcpy(key[vv++], x[bb++]); 

     for (y = 0; y < i; ++y) 
      free(x[y]); 
     free(x);           

     cnt += i; 
    } 
} 

int main(void) 
{ 
    int i; 
    char *key[LENGTH] = { "Hi", "this", "is", "a", "test" }; 

    printf("Before mergesort:\n"); 
    for (i = 0; i < LENGTH; ++i) 
     printf("%s ", key[i]); 
    putchar('\n'); 

    mergesort(key, LENGTH); 

    printf("After mergesort:\n"); 
    for (i = 0; i < LENGTH; ++i) 
     printf("%s ", key[i]); 
    putchar('\n'); 
    return 0; 
} 

Answer 1

void mergesort_pot2(char *key[], int n) 
{ 
    int j, k; 
    char **w; 

    w = calloc(n, sizeof(char*)); 
    for (k = 1; k < n; k *= 2) { 
     for (j = 0; j < n - k; j += 2 * k) 
      merge(key + j, key + j + k, w + j, k, k); 
     for (j = 0; j < n; ++j) 
      key[j] = w[j]; 
    } 
    free(w); 
} 

void mergesort(char *key[], int n) 
{ 
    int i, cnt = 0, v, b = 0, vv = 0, bb; 
    char **x; 

    while (n - cnt > 0) 
    { 
     for (i = 1; i < n - cnt; i *= 2); 
     if (i > n - cnt) 
      i /= 2; 

     x = calloc(i, sizeof(char *)); 

     v = 0; 
     while (v < i) 
      x[v++] = key[b++]; 

     mergesort_pot2(x, i);       

     bb = 0; 
     while (bb < i)         
      key[vv++]= x[bb++]; 

     free(x);           

     cnt += i; 
    } 
}