#include #define MAX_VALS 1000 int count, c, mid_index, low_index, high_index; int values[MAX_VALS], left[MAX_VALS/2+1], right[MAX_VALS/2+1]; int lows[32], mids[32], highs[32]; int ptr; int l_count, r_count, copypos; int leftpos, rightpos, mergepos; int l, r; double elapsed, startTime, endTime; FILE*fp; // ------------------------------------------------------------------- // loadFile // Purpose: // Read integers from a file into the shared values array. // Parameters: // fspec - path of the input file to read. // Returns: // Zero if the input file cannot be opened; otherwise no meaningful value. // Side effects: // Updates values and count, opens and closes the input file, and prints progress. // ------------------------------------------------------------------- loadFile(fspec) char *fspec; { count = 0; printf("READING INPUT FILE..."); fp = fopen(fspec, "rt"); if (!fp) { printf("\nERROR %d.\n", errno); return 0; } for (c = 0; c < MAX_VALS; c++) { if (fscanf(fp, "%d", &values[c]) != 1) { break ; } count++; } fclose(fp); printf("DONE.\n"); } // ------------------------------------------------------------------- // saveFile // Purpose: // Write the populated shared values array to a file. // Parameters: // fspec - path of the output file to create or replace. // Returns: // No meaningful value. // Side effects: // Writes count integers from values, opens and closes the file, and prints progress. // ------------------------------------------------------------------- saveFile(fspec) char *fspec; { printf("SAVING OUTPUT FILE..."); fp = fopen(fspec, "wt"); if (!fp) { printf("\nERROR %d.\n", errno); return ; } for (c = 0; c < count; c++) { fprintf(fp, "%d\n", values[c]); } fclose(fp); printf("DONE.\n"); } // ------------------------------------------------------------------- // merge // Purpose: // Merge the sorted left and right portions of the shared values array. // Parameters: // None; uses low_index, mid_index, high_index, and the shared arrays. // Returns: // No value; replaces the selected range in values with the merged order. // Side effects: // Updates values and uses the shared left and right temporary arrays. // ------------------------------------------------------------------- merge() { l_count = mid_index-low_index+1; r_count = high_index-mid_index; for (copypos = 0; copypos < l_count; copypos++) { left[copypos] = values[low_index+copypos]; } for (copypos = 0; copypos < r_count; copypos++) { right[copypos] = values[mid_index+1+copypos]; } leftpos = rightpos = 0; mergepos = low_index; while (leftpos < l_count && rightpos < r_count) { if (left[leftpos] <= right[rightpos]) { values[mergepos] = left[leftpos]; leftpos++; } else { values[mergepos] = right[rightpos]; rightpos++; } mergepos++; } for (l = leftpos; l < l_count; l++) { values[mergepos] = left[l]; mergepos++; } for (r = rightpos; r < r_count; r++) { values[mergepos] = right[r]; mergepos++; } } // ------------------------------------------------------------------- // mergesort // Purpose: // Recursively sort the range tracked by the shared index variables. // Parameters: // None; uses low_index and high_index, saving recursive bounds on stacks. // Returns: // No value; sorts the selected range of values in place. // Side effects: // Updates shared range indices and the recursion stack arrays. // ------------------------------------------------------------------- mergesort() { if (low_index >= high_index)return ; mid_index = low_index+(high_index-low_index)/2; // Save this range before recursion changes the shared index variables. ptr++; lows[ptr] = low_index; mids[ptr] = mid_index; highs[ptr] = high_index; high_index = mid_index; mergesort(); // Restore the parent range, then set the right-half bounds. low_index = lows[ptr]; mid_index = mids[ptr]; high_index = highs[ptr]; low_index = mid_index+1; mergesort(); low_index = lows[ptr]; mid_index = mids[ptr]; high_index = highs[ptr]; ptr--; merge(); } // ------------------------------------------------------------------- // doSort // Purpose: // Set the range to the populated values and time merge sorting it. // Parameters: // None; uses values and count. // Returns: // Elapsed sorting time in seconds. // Side effects: // Sorts values in place and prints progress. // ------------------------------------------------------------------- double doSort() { printf("SORTING ELEMENTS..."); startTime = Tgettime(); ptr = 0; low_index = 0; high_index = count-1; mergesort(); endTime = Tgettime(); printf("DONE.\n"); return endTime-startTime; } // ------------------------------------------------------------------- // main // Purpose: // Run the input, sort, output, and timing-report workflow. // Parameters: // None. // Returns: // One after the program completes. // Side effects: // Reads and writes files, sorts the shared values array, and prints results. // ------------------------------------------------------------------- int main() { printf("\n=======MERGESORT HiSoft C=======\n"); loadFile("C:\\INPUT.TXT"); if (count > 0) { elapsed = doSort(); saveFile("C:\\OUTPUT.TXT"); } printf("==========RUN COMPLETE==========\n"); printf("MERGESORT TOOK %f SECONDS.\n", elapsed); printf("================================\n"); evnt_keybd(); return 1; }