Question

Implement MERGE-SORT() algorithm that reads from a file named “inputHW02.txt” a list of double numbers (max = 3,000,000 numbers), sorts those numbers and indicates time consumption. This programming question will address the advantage of using iteration loops over recursive calls as well as using INSERTION-SORT() as a procedure in MERGESORT(). Your program must perform the following actions:
1. Opens the given file name and reads all double numbers. For simplicity, we assume this file only contains numbers and nothing else.

2. Implements the function INSERTION-SORT() that only sort an array of maximum 25 numbers. The idea is that INSERTION-SORT() will be used as a sub-procedure to sort any sub-array when its size is small enough.

3. Four versions of MERGE-SORT() namely a. MERGE-SORT-A(): Using recursive calls and NO INSERTION-SORT() as a sub-procedure b. MERGE-SORT-B(): Using ITERATIVE loops (i.e, NO recursion) and NO INSERTION-SORT() as a subprocedure. c. MERGE-SORT-C(): Using recursive calls and INSERTION-SORT() as a sub-procedure. d. MERGE-SORT-D(): Using ITERATIVE loops (i.e, NO recursion) and INSERTION-SORT() as a subprocedure.

Answer 1

solution:
1.program to read the numbers from file:-

FILE *f=fopen("inputHW02.txt");   

int intergersarray[10000]; //array to store values from text file

int i=0,num;

while(fscanf(f,%d,&num) && !feof(f)) //reads until it reaches the end of file

{

intergersarray[i]=num;

i++;

}

   fclose(f);

2.implementation of insertion sort as a sub procedure:

INSERTION_SORT(int array[], int n)

{

int i,val,j;

for(i=1;i

val=array[i];

j=i-1;

while(j>=0&&array[j]>val){

array[j+1]=array[j];

j--;

}

array[j+1]=key;

}

}

3.MERGE-SORT-A:

void mergesort(int array[],int l,int r){
if(l

int m=l+(r-1)/2

mergesort(array,l,m);

mergesort(array,m+1,r);

merge(array,l,m,r);

}

}

void merge(int array[],int l,int m,int r){

int i,j,k;

int p=m-l+1;

int q=r-m;

int L[p],R[q];

for(i=0;i

L[i]=array[l+i];

}

for(j=0;j

R[i]=array[m+1+j];

}

i=0;

j=0;

k=l;

while(i

if(L[i]<=R[i]){

arr[k]=L[i];

i++;

}

else{

array[k]=R[j];

j++;

}

k++;

   }

while(i

arr[k]=L[i];

i++;

k++;

}

while(j

arr[k]=R[j];

j++;

k++;

}

}

MERGE_SORT_B:-

  void mergeSort(int array[], int n)

{

int current;

int l;

for(current=1;current<=n-1;current = 2*current)

  {

  for (l=0;l

  {

int m=min(left+current-1,n-1);

int r=min(l+ 2*current-1,n-1);

  merge(arr,l,m,r);

  }

  }

}

void merge(int array[],int l,int m,int r){

int i,j,k;

int p=m-l+1;

int q=r-m;

int L[p],R[q];

for(i=0;i

L[i]=array[l+i];

}

for(j=0;j

R[i]=array[m+1+j];

}

i=0;

j=0;

k=l;

while(i

if(L[i]<=R[i]){

arr[k]=L[i];

i++;

}

else{

array[k]=R[j];

j++;

}

k++;

   }

while(i

arr[k]=L[i];

i++;

k++;

}

while(j

arr[k]=R[j];

j++;

k++;

}

}

MERGE_SORT_C:

here we are performing insertion sort in the insertion sort if the array size is less than 25.

void mergesort(int array[],int l,int r){

if(r-l <= 25){

insertion_sort(array,l,r);

   else{

int m=l+(r-1)/2

mergesort(array,l,m);

mergesort(array,m+1,r);

merge(array,l,m,r);

}

}

void insertion_sort(int array[],int l,int r){

int val;

for(i=l;i

val=array[i];

j=i-1;

while(j>=l&&array[j]>val){

array[j+1]=array[j];

j--;

}

array[j+1]=key;

}

}

void merge(int array[],int l,int m,int r){

int i,j,k;

int p=m-l+1;

int q=r-m;

int L[p],R[q];

for(i=0;i

L[i]=array[l+i];

}

for(j=0;j

R[i]=array[m+1+j];

}

i=0;

j=0;

k=l;

while(i

if(L[i]<=R[i]){

arr[k]=L[i];

i++;

}

else{

array[k]=R[j];

j++;

}

k++;

   }

while(i

arr[k]=L[i];

i++;

k++;

}

while(j

arr[k]=R[j];

j++;

k++;

}

}

MERGE_SORT_D:

void mergeSort(int array[], int n)

{

int current;

int l;

for(current=1;current<=n-1;current = 2*current)

  {

  for (l=0;l

  {

int m=min(left+current-1,n-1);

int r=min(l+ 2*current-1,n-1);

if(r-l<=25){

insertionsort(array,l,r);

else{

  merge(arr,l,m,r);

}

  }

  }

}

void insertion_sort(int array[],int l,int r){

int val;

for(i=l;i

val=array[i];

j=i-1;

while(j>=l&&array[j]>val){

array[j+1]=array[j];

j--;

}

array[j+1]=key;

}

}

void merge(int array[],int l,int m,int r){

int i,j,k;

int p=m-l+1;

int q=r-m;

int L[p],R[q];

for(i=0;i

L[i]=array[l+i];

}

for(j=0;j

R[i]=array[m+1+j];

}

i=0;

j=0;

k=l;

while(i

if(L[i]<=R[i]){

arr[k]=L[i];

i++;

}

else{

array[k]=R[j];

j++;

}

k++;

   }

while(i

arr[k]=L[i];

i++;

k++;

}

while(j

arr[k]=R[j];

j++;

k++;

}

}