int values[1000]; int numvals; int temp[1000]; // ------------------------------------------------------------------- // domerge // Purpose: // Merge two sorted portions of an integer array. // Parameters: // arr - array whose values are being sorted. // left - inclusive first index of the range. // mid - inclusive last index of the left half. // right - inclusive last index of the right half. // Returns: // No value; copies the merged range back into arr. // Side effects: // Uses the global temp array to stage the merged values. // ------------------------------------------------------------------- domerge(arr,left,mid,right) int arr[]; int left,mid,right; $( int i,j,k; i=left; j=mid+1; k=left; while(i <= mid && j <= right) $( if(arr[i] <= arr[j]) temp[k++]=arr[i++]; else temp[k++]=arr[j++]; $) while(i <= mid) temp[k++]=arr[i++]; while(j <= right) temp[k++]=arr[j++]; for(i=left;i<=right;i++) arr[i]=temp[i]; $) // ------------------------------------------------------------------- // mergsort // Purpose: // Recursively divide an array range, sort each half, and merge them. // Parameters: // arr - array whose values are being sorted. // left - inclusive first index of the range. // right - inclusive last index of the range. // Returns: // No value; sorts the selected range of arr in place. // Side effects: // Reorders arr in place and uses the global temp array during merging. // ------------------------------------------------------------------- mergsort(arr,left,right) int arr[]; int left,right; $( int mid; if(left>=right) return; mid=(left+right)/2; mergsort(arr,left,mid); mergsort(arr,mid+1,right); domerge(arr,left,mid,right); $) // ------------------------------------------------------------------- // main // Purpose: // Run the input, sort, output, and timing-report workflow. // Parameters: // None. // Returns: // Zero when the program completes normally. // Side effects: // Reads and writes files and prints timing and completion messages. // ------------------------------------------------------------------- main() $( int elapsed; cprints("=====MERGESORT Deep Blue C=====\n"); loadfile(); elapsed=dosort(); savefile(); cprints("==========RUN COMPLETE==========\n"); printf("MERGESORT TOOK %d SECONDS.\n",elapsed); cprints("================================\n"); gets(); return 0; $) // ------------------------------------------------------------------- // fgets // Purpose: // Read one text record from a file, stopping at a line ending or limit. // Parameters: // data - destination buffer. // max - capacity of data, including its terminating null character. // fp - file handle to read from. // Returns: // data, containing the record as a null-terminated string. // Side effects: // Reads characters from the specified file handle. // ------------------------------------------------------------------- fgets(data,max,fp) char *data; int max,fp; $( int r,c,i; i=0; while(i 0) $( idx--; *str = tmp[idx]; str++; $) *str = '\0'; return str; $) // ------------------------------------------------------------------- // fputs // Purpose: // Write a string followed by the platform's line-ending character. // Parameters: // data - null-terminated string to write. // fp - file handle to write to. // Returns: // The result of the final character write, or the string-write error. // Side effects: // Writes the string and line ending to the specified file handle. // ------------------------------------------------------------------- fputs(data,fp) char *data; int fp; $( int r; r=cputs(data,fp); if(r<0) return r; return cputc(155,fp); $) // ------------------------------------------------------------------- // swap // Purpose: // Exchange the integers stored at two addresses. // Parameters: // a - pointer to the first integer; updated with the second value. // b - pointer to the second integer; updated with the first value. // Returns: // No value. // Side effects: // Changes the values stored at both pointers. // ------------------------------------------------------------------- swap(a,b) int *a; int *b; $( int temp; temp = *a; *a = *b; *b = temp; $) // ------------------------------------------------------------------- // loadfile // Purpose: // Read integer records from the input file into the global values array. // Parameters: // None; uses the fixed input path. // Returns: // No value. // Side effects: // Updates values and numvals and opens and closes the input file. // ------------------------------------------------------------------- loadfile() $( int fp,c; char tmp[16]; cprints("LOADING INPUT FILE..."); fp=open(2,4,0,"D:INPUT.TXT"); if(fp!=1) $( printf("ERROR [%d]: Cannot find input file.\n",fp); return; $) numvals=0; while(numvals<1000) $( fgets(tmp,16,2); if(tmp[0]=='*') break; values[numvals]=val(tmp); numvals++; $) cprints("DONE.\n"); cclose(2); return; $) // ------------------------------------------------------------------- // savefile // Purpose: // Write the populated global values array to the output file. // Parameters: // None; uses values and numvals. // Returns: // No value. // Side effects: // Creates the output file, writes one value per line, and closes the file. // ------------------------------------------------------------------- savefile() $( cprints("SAVING OUTPUT FILE..."); int fp,c; char tmp[16]; fp=open(2,8,0,"D:OUTPUT.TXT"); if(fp!=1) $( printf("ERROR [%d]: Cannot open output file.\n",fp); $) for(c=0;c