# Thread: Mergesort is of the devil

1. ## Mergesort is of the devil

So I'm having trouble getting my mergesort functions to work. The first function mergesort works fine, but then when the program calls merge it crashes. Heres mergesort:

Mergesort function
Code:
```void mergesort(struct comic **comics, int len)
{
struct comic *left;
struct comic *right;
int ct;

printf("test1");
if(len <= 1)
{
return;
}
else{

left = (struct comic*)calloc(len/2, sizeof(struct comic));

for(ct = 0; ct < len/2; ct++)
{
left[ct] = *comics[ct];
}
mergesort(&left, len/2);

right = (struct comic*)calloc(len - len/2, sizeof(struct comic));
for(ct = len/2; ct<len; ct++)
{
(right)[ct - len/2] = (*comics)[ct];
}
mergesort(&right, len - len/2);
printf("test1");
merge(&comics, &left, len/2, &right, len-len/2);

free(left);
free(right);
}//end else
}//End mergesort```
So when it gets done with the first few operations and hits the call for merge the program jumps to the merge function:

Merge function
Code:
```void merge(struct comic ***comicsc, struct comic **leftc, int leftlen, struct comic **rightc, int rightlen)
{
int comicsnum = 0;
int leftnum = 0;
int rightnum = 0;
//int righttst, lefttst;
printf("test1");
while(leftnum < leftlen && rightnum < rightlen)
{
if(leftc[leftnum]->issuenum <= rightc[rightnum]->issuenum)
{
**comicsc[comicsnum] = *leftc[leftnum];
comicsnum++;
leftnum++;
}
else
{
**comicsc[comicsnum] = *rightc[rightnum];
comicsnum++;
rightnum++;
}
}

printf("test");
//RIGHT WHEN IT GETS TO THE FOLLOWING LOOPS MY PROGRAM CRASHES
//I KNOW THIS BECAUSE IT STILL PRINTS THE PRINTF FUNCTION
//DIRECTLY ABOVE THIS
if(rightnum >= rightlen)
{

while(leftnum < leftlen)
{
**comicsc[comicsnum] = *leftc[leftnum];
comicsnum++;
leftnum++;
}
}
else
{
while(rightnum < rightlen)
{
printf("test1");
**comicsc[comicsnum] = *rightc[rightnum];
comicsnum++;
rightnum++;
}
}
//printf("test1");
}//End merge```
Does anyone see whats happening in those loops in the merge function that could be causing my program to crash?

Here's how I'm declaring everything and then calling it, its the entire main function of my program.
Code:
```main()
{
char filename[50], title[100], issue[100];
char *p;
char uscore = '_';
char blank = ' ';
int issuenum, numcomics, count = 0, cnt = 0, past = 0, pcnt = 0, tempcnt = 0;
struct comic *thecomics;
struct comic *temp;
FILE *f1;

printf("--------------------------------------------------------------------------------------");
printf("Welcome to the comic book sorter!\n");
printf("Please enter in the name of the file containing the comic books: ");
//fflush();
fgets(filename, sizeof(filename), stdin);

//Removes the \n that ENTER adds into the filename input
if((p = strchr(filename, '\n')) != NULL)
{
*p = '\0';
}

//Opens the file
f1 = fopen(filename, "r");
//fflush();

if(f1 != NULL)
{
fscanf(f1, "&#37;d", &numcomics);
system("pause");

thecomics = (struct comic*)calloc(numcomics, sizeof(struct comic));
temp = (struct comic*)calloc(numcomics, sizeof(struct comic));

do
{
fscanf(f1, "%s %d %s", title, &issuenum, issue);
cnt = 0;
//Checks for the _ in the string and replaces it with a "space"
do
{
if(title[cnt] == uscore)
{
title[cnt] = blank;
}
cnt++;
}while(cnt < 100);

//Checks for the _ in the string and replaces it with a "space"
cnt = 0;
do
{
if(issue[cnt] == uscore)
{
issue[cnt] = blank;
}
cnt++;
}while(cnt < 100);

strcpy(thecomics[count].title, title);
strcpy(thecomics[count].issue, issue);
thecomics[count].issuenum = issuenum;

count++;
}while(count < numcomics);

//Sorts by title and then mergesorts by comic number and prints
count = 0;
do
{
//Tests to see if the title has already been run
pcnt = count - 1;
while(pcnt >= 0)
{
if(strcmp(thecomics[count].title, thecomics[pcnt].title) == 0)
{
past = 1;
}
pcnt--;
}

if(past != 1)
{
tempcnt = 1;
cnt = count +1;
do
{
if(strcmp(thecomics[count].title, thecomics[cnt].title) == 0)
{

temp[0] = thecomics[count];
temp[tempcnt] = thecomics[cnt];
tempcnt++;
}
cnt++;
}while(cnt < numcomics);

mergesort(&temp, tempcnt);

cnt = 0;
printf("%s\n", temp[0].title);
while(cnt <= tempcnt)
{
printf("\t%d. %s\n", temp[cnt].issuenum, temp[cnt].issue);
cnt++;
}
}//End IF

count++;
}while(count < numcomics);
system("pause");

}//Close if
else
{
printf("There is nothing in the file or it doesn't exist!\n");
}//Close Else
system("pause");
}//Close main```

2. struct comic ***comicsc

what data this pointer to pointer to pointer is pointing?
could you show the array declarations and how you call the merge function?

3. Ok I added it to my original post above.

4. why this passing pointer to pointer crap? you never change the pointer - only the contents of the array it points

drop your & in mergesort(&temp, tempcnt); call - update the function prototype and body accordingly, do it for merge function as well

you do not work with pointer to pointer correctly

you want (*comics)[ct]; where you pass *comics[ct]; - so dropping pointer to pointer stuff will save you a headake

5. Originally Posted by vart
why this passing pointer to pointer crap? you never change the pointer - only the contents of the array it points

drop your & in mergesort(&temp, tempcnt); call - update the function prototype and body accordingly, do it for merge function as well

you do not work with pointer to pointer correctly

you want (*comics)[ct]; where you pass *comics[ct]; - so dropping pointer to pointer stuff will save you a headake
What do you mean by dropping pointer to pointer stuff? Could you take the declaration of one of my functions and change it so that I can see an example of what the rest should look like?

6. Code:
```void mergesort(struct comic *comics, int len)
{
printf("test1");
if(len <= 1)
{
return;
}
else
{
struct comic *left;
struct comic *right;
int ct;
left = calloc(len/2, sizeof(*left));

for(ct = 0; ct < len/2; ct++)
{
left[ct] = comics[ct];
}
mergesort(left, len/2);

right = calloc(len - len/2, sizeof(*right));
for(ct = len/2; ct<len; ct++)
{
right[ct - len/2] = comics[ct];
}
mergesort(right, len - len/2);
printf("test1");
merge(comics, left, len/2, right, len-len/2);

free(left);
free(right);
}//end else
}//End mergesort```

7. Originally Posted by vart
Code:
```void mergesort(struct comic *comics, int len)
{
printf("test1");
if(len <= 1)
{
return;
}
else
{
struct comic *left;
struct comic *right;
int ct;
left = calloc(len/2, sizeof(*left));

for(ct = 0; ct < len/2; ct++)
{
left[ct] = comics[ct];
}
mergesort(left, len/2);

right = calloc(len - len/2, sizeof(*right));
for(ct = len/2; ct<len; ct++)
{
right[ct - len/2] = comics[ct];
}
mergesort(right, len - len/2);
printf("test1");
merge(comics, left, len/2, right, len-len/2);

free(left);
free(right);
}//end else
}//End mergesort```
Ok, its working well now. Now I just have a few more kinks and it should be done. Thank you for all your help.

8. note that calloc is just waste of time - use malloc
and instead of loop - copying - use memmove

9. Looks like we have another three-star-programmer:

10. and don't forget your textbook. very handy for refreshers.

11. Maybe another performance option would be to save len/2 into a variable and use that variable instead of performing multiple identical division operations all over the place.