Auxilliary problems
Transcribed from the comments to the question.
For pity's sake, write compnode() sanely so that you don't have to go through the ghastly casts! Write it to take two const void * arguments and convert them in the code (it'll be a no-op):
int compnode(const void *v1, const void *v2)
{
const node *a = v1;
const node *b = v2;
return strcmp(a->name, b->name);
}
Also, don't use GCC's extensions. It is a bad habit if you have any pretensions towards writing portable code. Writing a+(n/2)*size where the argument is void *a is undefined behaviour per the C standard. You have to convert to char * (or some other type other than void *) before adding.
In genmnode(), you should be passing fcmp to the recursive functions and the merge() function, instead of passing compnode() directly.
Gannicus asked:
What do you mean pass fcmp instead of compnode?
WhozCraig explained:
[It] means you're passing your custom comparator function to the "generic" sort function as the fcmp parameter. Within that function, you blindly pass compnode to the recursive calls. You should be passing fcmp to those recursive calls instead, or your "generic" ideology just went out the window.
Primary problem
The primary problem is in your merge() function. The interface to that is most unusual. Normally, you pass two arrays to be merged, along with the size of each. You've chosen to pass one array and do some fancy footwork. The code in the main for loop in screws everything up.
void merge(void *a, int n, int size, int (*fcmp)(const void *, const void *)){
int i, j, k, mid=n/2;
void * temp = (void *)malloc(n*size);
for(i=0, j=mid, k=0; k<n; k++){
if((i<mid)&&(j>= n)){
memcpy(temp+(k*size), a+i*size, size);
i++;
}
else if((i<mid)&&(fcmp(a + i*size, a+j*size) <= 0)){
memcpy(temp+(k*size), a+j*size, size);
j++;
}
}
for(i=0, j=0; j<n; i++, j++)
memcpy(a+(j*size),temp+(i*size),size);
free(temp);
}
The trailing loop should be a single memcpy() operation, but what's there will work.
You have a single array, a, with a total of n elements of the given size. It must be treated as two sub-arrays, one of elements [0..mid), the LHS, and the other of elements [mid..n), the RHS. The ranges include the lower bound and exclude the upper bound.
The first condition inside the loop says 'if there is an element left in LHS and nothing left in RHS, copy the LHS element to the output'. The second condition says 'if there is an element left in the LHS (and, by elimination, there is an element in the RHS too), and the LHS compares smaller than the RHS, then copy the RHS element to the output'.
There are different and ultimately equivalent ways to write the merge process, but
normally the easiest to understand is:
while (item left in LHS and item left in RHS)
{
if (item in LHS is smaller than item in RHS)
copy LHS to result
else
copy RHS to result
}
while (item left in LHS)
copy item to result
while (item left in RHS)
copy item to result
The loop implemented does not come close to implementing that logic, or one of its equivalents.
Working code
Here's my diagnostic version of your code. The memset() at the top of merge() should not matter; you should be copying to temp and writing over all the X's. In practice, you are not.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node node;
struct node
{
long stdno;
char name[20];
};
static
void genswap(void *v1, void *v2, size_t size)
{
char v3[size];
memmove(v3, v1, size);
memmove(v1, v2, size);
memmove(v2, v3, size);
}
static
void print_node(const char *tag, node a[], int n)
{
printf("%s\n", tag);
for (int i = 0; i < n; i++)
printf("%2d: %p %2ld %s\n", i, &a[i], a[i].stdno, a[i].name);
}
static
void merge(void *a, int n, int size, int (*fcmp)(const void *, const void *))
{
int i, j, k, mid = n/2;
void *temp = (void *)malloc(n*size);
memset(temp, 'X', n*size);
printf("-->> %s\n", __func__);
print_node("Before Merge", (node *)a, n);
for (i = 0, j = mid, k = 0; k < n; k++)
{
if ((i < mid) && (j >= n))
{
memcpy(temp+(k*size), a+i*size, size);
i++;
}
else if ((i < mid) && (fcmp(a + i*size, a+j*size) <= 0))
{
memcpy(temp+(k*size), a+j*size, size);
j++;
}
}
print_node("Mid Merge", (node *)temp, n);
for (i = 0, j = 0; j < n; i++, j++)
memcpy(a+(j*size), temp+(i*size), size);
free(temp);
print_node("After Merge", (node *)a, n);
printf("<<-- %s\n", __func__);
}
static
void genmsort(void *a, int n, int size, int (*fcmp)(const void *, const void *))
{
if (n > 1)
{
genmsort(a, n/2, size, fcmp);
genmsort(a+(n/2)*size, n-n/2, size, fcmp);
merge(a, n, size, fcmp);
}
}
static
int compnode(const void *v1, const void *v2)
{
const node *a = v1;
const node *b = v2;
printf("%s: (%ld:%s) vs (%ld:%s)\n", __func__, a->stdno, a->name, b->stdno, b->name);
return(strcmp(a->name, b->name));
}
static
void init_node(node a[], int n)
{
for (int i = 0; i < n; i++)
{
a[i].stdno = i+1;
sprintf(a[i].name, "%li", a[i].stdno);
}
srand(8);
for (int i = 0; i < n; i++)
genswap(a+i, a+(rand()%n), sizeof(node));
}
int main(void)
{
int n = 10;
node *b = (node *)malloc(n*sizeof(node));
init_node(b, n);
print_node("Before:", b, n);
genmsort(b, n, sizeof(node), compnode);
print_node("After:", b, n);
free(b);
return 0;
}
