Merge Sort is looping continuously and going into segmentation fault

Question

I am trying to implement merge sort using arrays.My code is jumping into the loop and not stopping.I need to use Ctrll+Z to stop my program.Basically I am reading from a file and passing that array into mergesort function and then I write again into a file.After writing into a file I calculate the programming time and display it.Please check my below code.Thank you.

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

clock_t start=clock();
void mergesort(int *,int,int);
void merge(int *,int,int,int);
void writesortedrraytofile(int *,int);

static char *opfile=(char *)"output.txt";

int main(int argc,char* argv[])
{
        FILE *fp;
        char line[80];
        int array[1000000];
        int i=0,counter;
        int choice;


        printf("The command line arguments are:\n");
        printf("%d %s %s %s\n",argc,argv[0],argv[1],argv[2]);

        if(argc==3 && strcmp(argv[0],"./sorting")==0 && strcmp(argv[1],"input1.txt")==0 && strcmp(argv[2],"output.txt")==0)
        {
                printf("The command line arguments are correct.\n");
        }
        else
        {
                printf("The command line arguments are wrong.I am exiting.\n");
                exit (0);
        }
fp=fopen(argv[1],"r");
while(fgets(line,80,fp) !=NULL)
{
        sscanf(line,"%d",&array[i]);
        i++;
}
counter=i;
fclose(fp);
    mergesort(array,0,counter);
        }
        return 0;
}

void mergesort(int *temp,int begin,int end)
{
        int mid=0;
        if(begin<end)
        {
                mid=(begin+end)/2;
                mergesort(temp,begin,mid);
                mergesort(temp,mid+1,end);
        }
                merge(temp,begin,mid,end);
}

void merge(int *temp,int low,int mid,int high)
{
        int i,k;
        int *tmp = (int *) malloc((high - low +1)* sizeof(int));
        int begin1 = low;
        int end1 = mid;
        int begin2= mid +1;
        int end2 = high;

        for ( k = 0; begin1 <= end1 && begin2 <= end2; k++)
                if (temp[begin1] < temp[begin2])
                        tmp[k] = temp[begin1 ++];
                else
                        tmp[k] = temp[begin2 ++];
        while (begin1 <= end1)
                tmp[k++] = temp[begin1 ++];
        while (begin2 <= end2)
                tmp[k++] = temp[begin2 ++];
        for ( i =0;i < high -low +1; i ++)
                temp[low +i] = tmp[i];
        free(tmp);
        writesortedrraytofile(tmp,high-low+1);
        return;
}


void writesortedrraytofile(int *ssarray,int len)
{
        FILE *fp;
        fp=fopen(opfile,"w");
        for(int i=0;i<len;i++)
        fprintf(fp,"%d\n",ssarray[i]);
        fclose(fp);
        printf("The output file is generated.Please check it inside the directory.\n");
        printf("Time elapsed: %f\n", ((double)clock() - start) / CLOCKS_PER_SEC);
        return;
}

Answer 1

I didn't try the code by myself, but using such a big array as a local variable doesn't sound like a very good idea. You also don't do any boundary checks when reading into the file. This may corrupt your stack and lead to unpredictable results.

A better solution might be:

#define MAX_COUNT 1000000
int* array = (int*)malloc(MAX_COUNT * sizeof(int));

and

while((fgets(line,80,fp) !=NULL) && (i < MAX_COUNT))

Answer 2

In mergesort, you have written int mid=0. Instead do this:

int mid=(begin+end)/2;

That fixes segmentation fault. Now call writesortedrraytofile from at the end of main() method instead of from merge(). This will fix recursive output into output.txt.

int main(int argc,char* argv[])
{
   ...
   ...
   ...
  counter=i;
  fclose(fp)
  mergesort(array,0,counter);
  writesortedrraytofile(array,counter); // call writesortedrraytofile from here
}

After this you get sorted numbers in output.txt. Still there is one more problem. For input: (3, 4, 1, 5, 6, 7, 3, 9, 10) output is coming: (0, 1, 3, 3, 4, 5, 6, 7, 9). Not sure why last number is getting replaced by 0. This problem is certainly because of a bug in merge().

EDIT- Found the problem with 0 coming into output. The next fix would be to pass counter-1 instead of counter to mergesort(). After this programs works quite fine.

int main(int argc,char* argv[])
{
   ...
   ...
   ...
  counter=i;
  fclose(fp)
  mergesort(array,0,counter-1); // pass counter-1 instead of counter
  writesortedrraytofile(array,counter); // call writesortedrraytofile from here
}