Provide the missing code to implement the Merge() algorithm

found in the pic below in the area that says "Student provides missing code..."

//---------------------------------------------------

// Dr. Art Hanna

// Problem #35

// Problem35.c

//---------------------------------------------------

#include

#include

#include

#include

#include

#include "..\Random.h"

#define TRACE_MERGESORT

//---------------------------------------------------

int main()

//---------------------------------------------------

{

void DoMergeSort(FILE *DATA,const int n);

void DisplayFile(FILE *DATA,const int n);

void DoBinarySearch(const int datum,FILE *AFILE,const int L,const int R,

bool *found,int *record,int *numberCompares);

int n,LB,UB;

int i;

FILE *AFILE;

printf("n? "); scanf("%d",&n);

printf("LB? "); scanf("%d",&LB);

printf("UB? "); scanf("%d",&UB);

// Build binary file contents with n randomly-chosen integers from the interval [ LB,UB ]

SetRandomSeed();

AFILE = fopen("AFile.dat","w+b");

assert( AFILE != NULL );

for (i = 0; i

{

int datum = RandomInteger(LB,UB);

fwrite(&datum,sizeof(int),1,AFILE);

}

printf("Unsorted: "); DisplayFile(AFILE,n);

DoMergeSort(AFILE,n);

printf(" Sorted: "); DisplayFile(AFILE,n);

// Use Binary Search algorithm to search sorted binary file for every datum in [ LB,UB ]

{

int datum;

for (datum = LB; datum

{

bool found;

int record,numberCompares;

numberCompares = 0;

DoBinarySearch(datum,AFILE,0,n-1,&found,&record,&numberCompares);

if ( found )

printf("%5d compares: %5d found at record %5d ",numberCompares,datum,record);

else

printf("%5d compares: %5d not found ",numberCompares,datum);

}

}

fclose(AFILE);

system("PAUSE");

return( 0 );

}

//---------------------------------------------------

void DoMergeSort(FILE *DATA,const int n)

//---------------------------------------------------

{

void Merge(FILE *BFILE,const int p,FILE *CFILE,const int q,FILE *AFILE);

void CopyFile(FILE *SFILE,const int L,const int R,FILE *TFILE);

static int suffix = 0;

#if defined(TRACE_MERGESORT)

printf("Sort %5d records in FILE *%p ",n,DATA);

#endif

if ( n > 1 )

{

char BFileName[80+1];

FILE *BFILE;

char CFileName[80+1];

FILE *CFILE;

int s = (int) floor(n/2);

suffix++;

sprintf(BFileName,"BFile%d.dat",suffix);

BFILE = fopen(BFileName,"w+b");

assert( BFILE != NULL );

CopyFile(DATA,0,s-1,BFILE);

sprintf(CFileName,"CFile%d.dat",suffix);

CFILE = fopen(CFileName,"w+b");

assert( CFILE != NULL );

CopyFile(DATA,s,n-1,CFILE);

#ifdef TRACE_MERGESORT

printf("%s (FILE *%p) contains %5d records ",BFileName,BFILE,(s-1)-0+1);

printf("%s (FILE *%p) contains %5d records ",CFileName,CFILE,(n-1)-s+1);

#endif

DoMergeSort(BFILE,(s-1)-0+1);

DoMergeSort(CFILE,(n-1)-s+1);

Merge(BFILE,(s-1)-0+1,CFILE,(n-1)-s+1,DATA);

fclose(BFILE); remove(BFileName);

fclose(CFILE); remove(CFileName);

}

}

//---------------------------------------------------

void CopyFile(FILE *SFILE,const int L,const int R,FILE *TFILE)

//---------------------------------------------------

{

void SET(FILE *DATA,const int record,const int datum);

int GET(FILE *DATA,const int record);

int record;

for (record = L; record

SET(TFILE,record-L,GET(SFILE,record));

}

//---------------------------------------------------

void Merge(FILE *BFILE,const int p,FILE *CFILE,const int q,FILE *AFILE)

//---------------------------------------------------

{

void SET(FILE *DATA,const int record,const int datum);

int GET(FILE *DATA,const int record);

Student provides missing code to implement the Merge() algorithm

found in Section 5.1 on page 72 the text book.

}

//---------------------------------------------------

void DisplayFile(FILE *DATA,const int n)

//---------------------------------------------------

{

int i;

for (i = 0; i

printf("%5d",GET(DATA,i));

printf(" ");

}

//---------------------------------------------------

void SET(FILE *DATA,const int record,const int datum)

//---------------------------------------------------

{

fseek(DATA,record*sizeof(int),SEEK_SET);

fwrite(&datum,sizeof(int),1,DATA);

}

//---------------------------------------------------

int GET(FILE *DATA,const int record)

//---------------------------------------------------

{

int datum;

fseek(DATA,record*sizeof(int),SEEK_SET);

fread(&datum,sizeof(int),1,DATA);

return( datum );

}

//---------------------------------------------------

void DoBinarySearch(const int datum,FILE *DATA,const int L,const int R,

bool *found,int *record,int *numberCompares)

//---------------------------------------------------

{

/*

Do binary search of records L through R, inclusive, searching for datum

in the binary file DATA. Return *found as true when datum is found, otherwise

return false. When datum is found, return *record [ L,R ], otherwise

*record is meaningless. Count three-way compares of datum with *numberCompares.

*/

if ( L > R )

*found = false;

else

{

*record = (L+R)/2;

*numberCompares += 1;

if ( datum

DoBinarySearch(datum,DATA,L,*record-1,found,record,numberCompares);

else if ( datum == GET(DATA,*record) )

*found = true;

else // if ( datum > GET(DATA,*record) )

DoBinarySearch(datum,DATA,*record+1,R,found,record,numberCompares);

}

}

//--------------------------------------------------

// Dr. Art Hanna

// Random.c

//--------------------------------------------------

#include

#include

#include

#include

#include ".\Random.h"

//--------------------------------------------------

void SetRandomSeed(void)

//--------------------------------------------------

{

srand(time(NULL));

}

//--------------------------------------------------

int RandomInteger(int LB,int UB)

//--------------------------------------------------

{

return( (int) (RandomReal()*(UB-LB+1)) + LB );

}

//--------------------------------------------------

double RandomReal()

//--------------------------------------------------

{

int R;

do

R = rand();

while ( R == RAND_MAX );

return( (double) R/RAND_MAX );

}

//--------------------------------------------------

bool RandomBoolean(double bias)

//--------------------------------------------------

{

return( RandomReal()

}

//--------------------------------------------------

char RandomCharacter(char characters[],int size)

//--------------------------------------------------

{

return( characters[RandomInteger(0,(size-1))] );

}

//--------------------------------------------------

// Dr. Art Hanna

// Random.h

//--------------------------------------------------

#ifndef RANDOM_H

#define RANDOM_H

#include

// initialize the "seed" used by the "rand()" function in

void SetRandomSeed(void);

// return uniformly, randomly chosen integer from [ LB,UB ]

int RandomInteger(int LB,int UB);

// return uniformly, randomly real number chosen from [ 0.0,1.0 )

double RandomReal(void);

// return randomly-chosen boolean with bias from { false,true }

bool RandomBoolean(double bias);

// return uniformly, randomly-chosen character from characters[i], i in [ 0,(size-1) ]

char RandomCharacter(char characters[],int size);

#endif

5.1 Mergesort Mergesort is a perfect example of a successful application of the divide-and- conquer technique. It sorts a given array A[0..n - 1] by dividing it into two halves 0-Ln/2]-1] and ALn/2]..n-1], sorting each of them recursively, and then merging the two smaller sorted arrays into a single sorted one ALGORITHM Mergesort(A[0.n -1]) //Sorts array A[0..n - 1] by recursive mergesort //Input: An array A[0..n - 1] of orderable elements //Output: Array A[0..n - 1] sorted in nondecreasing order if n> copy A[0.n/2 1 to B[0. In/2]-1] copy ALn/2]..n-1] to C [0.. /21-1] Mergesort(B[0..1n/2]-1]) Mergesort (C[0.. [n/21-1]) Merge(B, C, A) l/see below The merging of two sorted arrays can be done as follows. Two pointers (array indices) are initialized to point to the first elements of the arrays being merged The elements pointed to are compared, and the smaller of them is added to a new array being constructed; after that, the index of the smaller element is incremented to point to its immediate successor in the array it was copied from. This operation is repeated until one of the two given arrays is exhausted, and then the remaining elements of the other array are copied to the end of the new array ALGORITHM Merge(B[O.p - 1 C[0.q - 1], A[0..p +q -1]) //Merges two sorted arrays into one sorted array /Input: Arrays B[0..p - 11 and C[O..q- 11 both sorted /Output: Sorted array A[0..p+q 1 of the elements of B and C while i