1. my mergeSort

Hey, I am trying to make a mergeSort to sort an array of

Code:
```struct student {
char first[30];
char last[30];
int month;
int day;
int year; //this is not looked at while sorting
}```
This is my function(s):

Code:
```//sorts left and right halves and then merges them together; recursively called
//to get smaller halves
void mergeSort(struct student* list[], int low, int high) {
if(low<high) {
int mid=(low+high)/2;
printf("\nMerge LOW,MID,HIGH: %d-%d-%d\n",low,mid,high);
mergeSort(list,low,mid);
mergeSort(list,mid+1,high);
merge(list,low,mid+1,high);
}
}

//takes a second array and organizes each half of the array alphabetically, and then
//replaces the values in the array
void merge(struct student* list[], int low, int mid, int high) {
int length=high-low+1;
printf("\nLength: %d\n",length);
struct student* temp[1002];
int count1=low, count2=mid;
int index=0;
while((count1<mid) && (count2<high)) {
if(compareAge(list[count1],list[count2])==-1) {
temp[index]=list[count1];
index++;
count1++;
}
else {
temp[index]=list[count2];
index++;
count2++;
}
}
int i;
if(count1<mid) {
for(i=index;i<length;i++) {
temp[i]=list[count1];
count1++;
}
}
else if(count2<high) {
for(i=index;i<length;i++) {
temp[i]=list[count2];
count2++;
}
}
for(i=0;i<high;i++) {
if(temp[i]->first=="NULL" || temp[i]->last=="NULL") {
printf("Temp[%d]: NULL",i);
}
else
printf("Temp[%d]: %s %s\n",i,temp[i]->first,temp[i]->last);
}
for(i=low;i<=high;i++) {
list[i]=temp[i-low];
}
for(i=0;i<high;i++) {
if(list[i]->first=="NULL" || list[i]->last=="NULL") {
printf("List[%d]: NULL",i);
}
else
printf("List[%d]: %s %s\n",i,list[i]->first,list[i]->last);
}
}```
Some helpful advice please The error produced is that it crashes randomly in the middle of printing. What's worse, based on previous output before it prints the whole and finished. However, if I take out the prints, then it finishes and the program does NOT crash. However, it prints them out of order. Anybody can see what's wrong with my mergeSort?

2. Originally Posted by Soulzityr
The error produced is that it crashes randomly in the middle of printing.
You just need to run it once thru a debugger and find the cause of the crash. Please tell us what platform you are using so someone can explain how to use a debugger here, it is not hard.

One observation:
Code:
```void mergeSort(struct student* list[], int low, int high) {
if(low<high) {
int mid=(low+high)/2;
printf("\nMerge LOW,MID,HIGH: %d-%d-%d\n",low,mid,high);
mergeSort(list,low,mid);
mergeSort(list,mid+1,high);
merge(list,low,mid+1,high);
}
}```
The red line is problematic. It occurs first. Given the list:
2 3 4 5 6 7 8
We now go: "2 3 4 5" then "2 3" then "2 2" then "2 2" then "2 2" then "2 2" ad infinitum.

3. really? cuz i copied the formula straight from my instructor's website; it was offered to us since we had to do a lot more with the program. but hmm i see the problem. but isn't that covered with the if(low<high) part? that makes it so it wont happen, right?

btw i use dev-cpp

4. Originally Posted by Soulzityr
really? cuz i copied the formula straight from my instructor's website; it was offered to us since we had to do a lot more with the program. but hmm i see the problem. but isn't that covered with the if(low<high) part? that makes it so it wont happen, right?
Yeah okay yer right. It will bounce a back and complete the recursion from the last two elements. So the problem is in the other function.

btw i use dev-cpp
Windows or linux?

5. hmm which function, you mean the merge? yes...but i cant seem to find the problem. as far as i can tell, it should be working just fine...what more information do i need to show here to help address the issue? the output, etc?

and i use windows 7

6. No, you need to run it thru a debugger. The idea is, you compile the code with some symbols included (by the compiler -- you don't have to add change anything) in the executable so that the debugger can run the executable and identify the instruction during which "the crash" occurred. That instruction may be a line from your code, or (often enough) something within the standard (or other) library due to some kind of mis-use. In that case you can do a "backtrace" and in the end, find the exact line of code which resulted in "the crash".

This is almost always a major clue about what went wrong. Me scrutinizing code that I haven't run/can't isn't always effective (as we just saw), and this kind of extrapolates into a problem whereby the person who wrote the code cannot see the error either, even when they can run it. Which that happens to everyone and that is why there are debuggers and also why, sooner or later, you will be learning to use one.

Unfortunately, I don't program on windows or use dev-cpp so I can't help you with that part.

7. This is a recursive mergesort that you might compare with the program you have:

It appears to work, but has not been thoroughly tested:

Code:
```#include <stdio.h>
#include <stdlib.h>
#define MAX 200

void merge(int A[], int Index[], int l, int m, int r);
void mergesort(int *A, int *Index, int l, int r);
void printIt(int *A);

int main() {

int i;
int *A, *Index;

A = malloc(MAX * sizeof(int));
Index = malloc(MAX * sizeof(int));

if(!A || !Index) {
printf("memory allocation failed - terminating program");
return 1;
}
for(i = 0; i < MAX; i++) {
A[i] = rand() % 1000;
Index[i] = 0;
}

printf("\n\n  Unsorted Data\n");
printIt(A);
getchar();

mergesort(A, Index, 0, MAX-1);
printf("\n\n Sorted Data\n");
printIt(A);

free(A);
free(Index);
i = getchar();
return 0;
}
void mergesort(int *A, int *Index, int l, int r) {
int m;
if (l < r) {
m = (l + r) /2;
mergesort(A, Index, l, m);
mergesort(A, Index, m + 1, r);
merge(A, Index, l, m, r);
}
}

/* First, index m in the middle between lo and hi is determined. Then the
first part of the sequence (from lo to m) and the second part (from m+1
to hi) are sorted by recursive calls of mergesort. Then the two sorted halves
are merged by merge(). Recursion ends when lo = hi, i.e. when a sub-sequence
consists of only one element.
*/

void merge(int A[], int Index[], int l, int m, int r)
{
int i, j, k;

/* copy A to temp array Index */
for (i = l; i <= r; i++)
Index[i] = A[i];

i = l; j = m + 1; k = l;
/* copy back to A */
while (i <= m && j <= r)
if (Index[i] <= Index[j])
A[k++] = Index[i++];
else
A[k++] = Index[j++];

/* copy back remaining elements of first half (if any)  */
while (i <= m)
A[k++] = Index[i++];
}
/*Merge() does most of the work in Mergesort. The two halves are first copied
into an extra array, Index. Then both halves are checked by the indicies i and
j, and the next number is copied back to array A, each time through the
while loop of merge();
*/
void printIt(int A[]) {
int i;
for(i = 0; i < MAX; i++)
printf(" %3d ", A[i]);

}```
The output is good to see both the sorted, and unsorted int's, on the same page, if you keep the number of elements below 250 or so.

8. hmm the mergesort technique you have looks exactly the same as mine o_O is there any difference? because its not sorting correctly...

9. Do you expect this:
Code:
`if(temp[i]->first=="NULL" || temp[i]->last=="NULL") {`
to do anything useful? (Hint: == does not compare strings.)

I'm also even wondering why that's there. Do you try to sort more items than there are?

10. oh no sorry i was doing that earlier to try and debug, cuz it was crashing so i figured it was trying to print NULL stuff

11. These are wrong:
Code:
```   if(count1<mid) {
for(i=index;i<length;i++) {
temp[i]=list[count1];
count1++;
}
}
else if(count2<high) {
for(i=index;i<length;i++) {
temp[i]=list[count2];
count2++;
}
}```
You want to copy items until i is equal to mid in the first case, and i is equal to high in the second case. The variable 'length' should be removed.

You may also have some off by one errors, depending on how you call 'mergesort'.

12. when i changed from length to mid/high the program now crashes, so what does that mean? I think you're right that length there is wrong but now it crashes pretty early in trying to sort them.

what is an "off by one" error?

btw i dont know how im using the debugger. lol...ive been trying to use it but i guess i dont understand what it's telling me.

13. Originally Posted by Soulzityr
what is an "off by one" error?
Aka, the fencepost error:

Off-by-one error - Wikipedia, the free encyclopedia

Easy to make, but usually also easy to identify and fix.

btw i dont know how im using the debugger. lol...ive been trying to use it but i guess i dont understand what it's telling me.
A little googling implies to me that dev-cpp used gdb on windows via a GUI. I can't help you with the gui, but try "gdb" at the command line to see if it exists. If it does I can explain how to find the seg fault here, and once you've seen gdb running on the command line probably the GUI will start to make more sense.

14. Originally Posted by Soulzityr
when i changed from length to mid/high the program now crashes, so what does that mean? I think you're right that length there is wrong but now it crashes pretty early in trying to sort them.
That shouldn't happen. Can you show us what the change looks like please?

15. you mean as in the output? or in the code?

Code:
```   if(count1<mid) {
for(i=index;count1<mid;i++) { //for(i=index;i<length;i++) doesnt crash
temp[i]=list[count1];
count1++;
}
}
else if(count2<high) {
for(i=index;count2<high;i++) { //for(i=index;i<length;i++) doesnt crash
temp[i]=list[count2];
count2++;
}```