PROGRAM MERGESRT; CONST MAXVALS = 1000; TYPE TINTARRAY = ARRAY[1..MAXVALS] OF LONGINT; VAR VALUES: TINTARRAY; TEMP: TINTARRAY; COUNT: LONGINT; CODE: INTEGER; ELAPSED: REAL; {-------------------------------------------------------------------- Purpose: Read integer records from the named file into VALUES. Parameters: FILESPEC - path of the input file to read. Returns: No value; updates the shared VALUES array and COUNT. Side effects: Opens and closes the input file and prints progress. --------------------------------------------------------------------} PROCEDURE READFILE(CONST FILESPEC: STRING); VAR INPUTFILE: TEXT; LINE: STRING; BEGIN WRITE('READING INPUT FILE...'); ASSIGN(INPUTFILE,FILESPEC); RESET(INPUTFILE); COUNT := 0; WHILE NOT EOF(INPUTFILE) DO BEGIN READLN(INPUTFILE,LINE); IF LINE <> '' THEN BEGIN INC(COUNT); VAL(LINE,VALUES[COUNT],CODE); END; END; CLOSE(INPUTFILE); WRITELN('DONE.'); END; {-------------------------------------------------------------------- Purpose: Write the populated VALUES array to the named file. Parameters: FILESPEC - path of the output file to create or replace. Returns: No value; writes one integer per output line. Side effects: Creates and closes the output file and prints progress. --------------------------------------------------------------------} PROCEDURE SAVEFILE(CONST FILESPEC: STRING); VAR OUTPUTFILE: TEXT; INDEX: LONGINT; BEGIN WRITE('SAVING OUTPUT FILE...'); ASSIGN(OUTPUTFILE,FILESPEC); REWRITE(OUTPUTFILE); FOR INDEX := 1 TO COUNT DO WRITELN(OUTPUTFILE,VALUES[INDEX]); CLOSE(OUTPUTFILE); WRITELN('DONE.'); END; {-------------------------------------------------------------------- Purpose: Merge the sorted subranges VALUES[LEFT..MIDDLE] and VALUES[MIDDLE+1..RIGHT]. Parameters: LEFT, MIDDLE, RIGHT - inclusive range boundaries. Returns: No value; updates the selected VALUES range in place. Side effects: Uses TEMP to stage merged values before copying them back. --------------------------------------------------------------------} PROCEDURE MERGE(LEFT, MIDDLE, RIGHT: LONGINT); VAR L1, M, L2: LONGINT; BEGIN L1 := LEFT; M := MIDDLE + 1; L2 := LEFT; WHILE (L1 <= MIDDLE) AND (M <= RIGHT) DO BEGIN IF VALUES[L1] <= VALUES[M] THEN BEGIN TEMP[L2] := VALUES[L1]; INC(L1); END ELSE BEGIN TEMP[L2] := VALUES[M]; INC(M); END; INC(L2); END; WHILE L1 <= MIDDLE DO BEGIN TEMP[L2] := VALUES[L1]; INC(L1); INC(L2); END; WHILE M <= RIGHT DO BEGIN TEMP[L2] := VALUES[M]; INC(M); INC(L2); END; FOR L2 := LEFT TO RIGHT DO VALUES[L2] := TEMP[L2]; END; {-------------------------------------------------------------------- Purpose: Recursively split and sort VALUES[LEFT..RIGHT], then merge. Parameters: LEFT, RIGHT - inclusive bounds of the range to sort. Returns: No value; sorts the selected VALUES range in place. Side effects: Recursively updates VALUES and the shared TEMP array. --------------------------------------------------------------------} PROCEDURE MERGESORT(LEFT, RIGHT: LONGINT); VAR MIDDLE: LONGINT; BEGIN IF LEFT >= RIGHT THEN EXIT; MIDDLE := LEFT + (RIGHT - LEFT) DIV 2; MERGESORT(LEFT, MIDDLE); MERGESORT(MIDDLE + 1, RIGHT); MERGE(LEFT, MIDDLE, RIGHT); END; {-------------------------------------------------------------------- Purpose: Time sorting the populated VALUES array. Parameters: None; uses the shared VALUES array and COUNT. Returns: Elapsed sorting time in seconds. Side effects: Sorts VALUES in place and prints progress. --------------------------------------------------------------------} FUNCTION DOSORT: REAL; VAR STARTTIME, ENDTIME: LONGINT; BEGIN WRITE('SORTING ELEMENTS...'); STARTTIME := MEM[$40:$6C]; IF COUNT > 1 THEN MERGESORT(1, COUNT); ENDTIME := MEM[$40:$6C]; WRITELN('DONE.'); DOSORT := (ENDTIME - STARTTIME) / 18.2; END; BEGIN WRITELN('========MERGESORT PASCAL========'); READFILE('C:/INPUT.TXT'); ELAPSED := DOSORT; SAVEFILE('C:/OUTPUT.TXT'); WRITELN('==========RUN COMPLETE=========='); WRITELN('MERGESORT TOOK ', ELAPSED:0:6, ' SECONDS.'); WRITELN('================================'); END.