Question

Write a function in C that uses the Merge Sort sorting algorithm with arrays. The function must not be void and must output type int*

i.e. it must take the form:

int* merge_sort(int a[], int n)

where a[ ] is the input matrix and n is the size of the matrix. You may use an auxiliary functions such as "merge." The returned array should be sorted using merge_sort and should not modify the array that was input (a[ ] ).

Answer 1

Hi,

I am attaching the C file as well as pasting it here. You have to create an input file for containing the array elements in a file called array.txt. A sample of this array.txt is also sent for use as an example.

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
int *merge(int left[], int right[], int n)
{
  int *ord, i=0, j=0, k;
  ord = malloc(sizeof(int)*n);
  while((i<n/2) && (j<n-n/2)){
      if(left[i] < right[j]){
          *(ord+i+j) = left[i];
          i++;
        }
      else{
          *(ord+i+j) = right[j];
          j++;
          }
    }
  while(i!=n/2){
       *(ord+i+j) = left[i];
       i++; 
    }
  while(j!=n-n/2){
       *(ord+i+j) = right[j];
       j++; 
    }
  return ord;      
 }


int *merge_sort(int *arr, int n){
      int k = 0, *left, *right, *ord;
      ord = malloc(sizeof(int)*n);
      left = malloc(sizeof(int)*(n/2));
      right = malloc(sizeof(int)*(n-(n/2)));
      if (n<2){
         ord = arr;
      }else{
         for(k=0; k<n/2; k++)
             *(left + k) = *(arr + k);
         for(k=n/2; k<n; k++)
             *(right + k -(n/2)) = *(arr + k);

         left = merge_sort(left, n/2);
         right = merge_sort(right, n-(n/2));
         ord = merge(left, right, n);
      }      
      return ord;
}

int main(){
     FILE *inp;
     inp = fopen("array.txt", "r");
     if(!inp) printf("Error");

     int tot = 100;//the max no. of elements
     
     int *array,i,n;
     array = malloc(sizeof(int)*tot);
     
     int indice = 0;
     while(fscanf(inp,"%d", (array + indice)) != EOF) indice++;

     int *ord = merge_sort(array, indice);

     int k;
     for(k=0; k<indice; k++) printf("%d: %d \n",k, *(ord+k));


     fclose(inp);     
}

Array.txt.

14
7
2
9
31
45
87
34

Output:

Some screenshots of the file

Hope this helps!