IDENTIFICATION DIVISION. PROGRAM-ID. MERGE-SORT. ENVIRONMENT DIVISION. CONFIGURATION SECTION. INPUT-OUTPUT SECTION. FILE-CONTROL. SELECT SORTING-INPUT ASSIGN TO "D:/Sorting/Sorting_Input.txt" ORGANIZATION IS LINE SEQUENTIAL. SELECT SORTING-OUTPUT ASSIGN TO "D:/Sorting/Output_COBOL.TXT" ORGANIZATION IS LINE SEQUENTIAL. DATA DIVISION. FILE SECTION. FD SORTING-INPUT. 01 INPUT-LINE PIC X(20). FD SORTING-OUTPUT. 01 OUTPUT-LINE PIC -9(9). WORKING-STORAGE SECTION. 01 END-OF-FILE PIC X VALUE "F". 01 VALUE-COUNT PIC 9(4) VALUE 0. 01 START-TIME. 05 START-HOURS PIC 99. 05 START-MINS PIC 99. 05 START-SECS PIC 99. 05 START-MSECS PIC 99. 01 END-TIME. 05 END-HOURS PIC 99. 05 END-MINS PIC 99. 05 END-SECS PIC 99. 05 END-MSECS PIC 99. 01 START-TOT-SECS PIC 9(5)V99. 01 END-TOT-SECS PIC 9(5)V99. 01 ELAPSED-SECS PIC 9(5)V99. 01 THE-VALUES. 05 VALUE-ENTRY OCCURS 1000 TIMES PIC S9(9) COMP-5. 01 MERGE-TEMP-VALUES. 05 MERGE-TEMP-ENTRY OCCURS 1000 TIMES PIC S9(9) COMP-5. 01 SAVE-FILE-VARS. 02 SF-INDEX PIC 9(4). 01 MERGE-VARS. 02 MERGE-WIDTH PIC 9(4). 02 MERGE-LEFT PIC 9(4). 02 MERGE-MID PIC 9(4). 02 MERGE-RIGHT PIC 9(4). 02 MERGE-I PIC 9(4). 02 MERGE-J PIC 9(4). 02 MERGE-K PIC 9(4). PROCEDURE DIVISION. *> ----------------------------------------------------------------- *> MAIN-PROCEDURE *> Purpose: Coordinate reading, sorting, writing, and time reporting. *> Parameters: None; uses the program's working-storage fields. *> Returns: No value; STOP RUN ends the program. *> Side effects: Reads and writes files and displays the elapsed time. *> ----------------------------------------------------------------- MAIN-PROCEDURE. DISPLAY "========MERGESORT COBOL=========" PERFORM READ-FILE PERFORM DO-SORT PERFORM SAVE-FILE COMPUTE START-TOT-SECS = START-HOURS * 3600 + START-MINS * 60 + START-SECS + START-MSECS / 100 COMPUTE END-TOT-SECS = END-HOURS * 3600 + END-MINS * 60 + END-SECS + END-MSECS / 100 COMPUTE ELAPSED-SECS = END-TOT-SECS - START-TOT-SECS IF ELAPSED-SECS < 0 ADD 86400 TO ELAPSED-SECS END-IF DISPLAY "==========RUN COMPLETE==========" DISPLAY "MERGESORT TOOK " ELAPSED-SECS " SECONDS." DISPLAY "================================" STOP RUN. *> ----------------------------------------------------------------- *> READ-FILE *> Purpose: Read integer records into VALUE-ENTRY and set VALUE-COUNT. *> Parameters: None; reads SORTING-INPUT into shared working storage. *> Returns: No value; updates VALUE-ENTRY, VALUE-COUNT, and END-OF-FILE. *> Side effects: Opens and closes the input file and displays progress. *> ----------------------------------------------------------------- READ-FILE. DISPLAY "READING INPUT FILE..." WITH NO ADVANCING OPEN INPUT SORTING-INPUT PERFORM UNTIL END-OF-FILE = "T" READ SORTING-INPUT AT END MOVE "T" TO END-OF-FILE NOT AT END IF VALUE-COUNT >= 1000 DISPLAY "ERROR: INPUT EXCEEDS 1000 VALUES." STOP RUN RETURNING 1 END-IF ADD 1 TO VALUE-COUNT MOVE FUNCTION NUMVAL(INPUT-LINE) TO VALUE-ENTRY(VALUE-COUNT) END-READ END-PERFORM CLOSE SORTING-INPUT DISPLAY "DONE.". *> ----------------------------------------------------------------- *> SAVE-FILE *> Purpose: Write VALUE-COUNT integers from VALUE-ENTRY to SORTING-OUTPUT. *> Parameters: None; uses VALUE-ENTRY and VALUE-COUNT. *> Returns: No value; writes and closes the output file. *> Side effects: Opens the output file and displays progress. *> ----------------------------------------------------------------- SAVE-FILE. DISPLAY "SAVING OUTPUT FILE..." WITH NO ADVANCING OPEN OUTPUT SORTING-OUTPUT PERFORM VARYING SF-INDEX FROM 1 BY 1 UNTIL SF-INDEX > VALUE-COUNT MOVE VALUE-ENTRY(SF-INDEX) TO OUTPUT-LINE WRITE OUTPUT-LINE END-PERFORM CLOSE SORTING-OUTPUT DISPLAY "DONE.". *> ----------------------------------------------------------------- *> DO-SORT *> Purpose: Time a call to MERGESORT. *> Parameters: None; sorts the shared VALUE-ENTRY array. *> Returns: No value; stores start and end times in working storage. *> Side effects: Updates time fields and displays sort progress. *> ----------------------------------------------------------------- DO-SORT. DISPLAY "SORTING ELEMENTS..." WITH NO ADVANCING ACCEPT START-TIME FROM TIME PERFORM MERGESORT ACCEPT END-TIME FROM TIME DISPLAY "DONE.". *> ----------------------------------------------------------------- *> THE-MERGE *> Purpose: Merge the sorted left and right portions of VALUE-ENTRY. *> Parameters: MERGE-LEFT, MERGE-MID, MERGE-RIGHT define the inclusive *> ranges; all state is held in MERGE-VARS and VALUE-ENTRY. *> Returns: No value; writes the combined range back to VALUE-ENTRY. *> Side effects: Uses MERGE-TEMP-VALUES as temporary storage. *> ----------------------------------------------------------------- THE-MERGE. MOVE MERGE-LEFT TO MERGE-I COMPUTE MERGE-J = MERGE-MID + 1 MOVE MERGE-LEFT TO MERGE-K PERFORM UNTIL MERGE-I > MERGE-MID OR MERGE-J > MERGE-RIGHT IF VALUE-ENTRY(MERGE-I) <= VALUE-ENTRY(MERGE-J) MOVE VALUE-ENTRY(MERGE-I) TO MERGE-TEMP-ENTRY(MERGE-K) ADD 1 TO MERGE-I ELSE MOVE VALUE-ENTRY(MERGE-J) TO MERGE-TEMP-ENTRY(MERGE-K) ADD 1 TO MERGE-J END-IF ADD 1 TO MERGE-K END-PERFORM PERFORM UNTIL MERGE-I > MERGE-MID MOVE VALUE-ENTRY(MERGE-I) TO MERGE-TEMP-ENTRY(MERGE-K) ADD 1 TO MERGE-I ADD 1 TO MERGE-K END-PERFORM PERFORM UNTIL MERGE-J > MERGE-RIGHT MOVE VALUE-ENTRY(MERGE-J) TO MERGE-TEMP-ENTRY(MERGE-K) ADD 1 TO MERGE-J ADD 1 TO MERGE-K END-PERFORM PERFORM VARYING MERGE-K FROM MERGE-LEFT BY 1 UNTIL MERGE-K > MERGE-RIGHT MOVE MERGE-TEMP-ENTRY(MERGE-K) TO VALUE-ENTRY(MERGE-K) END-PERFORM. *> ----------------------------------------------------------------- *> MERGESORT *> Purpose: Bottom-up merge adjacent runs, doubling their width each pass. *> Parameters: None; uses VALUE-COUNT and the shared merge variables. *> Returns: No value; sorts VALUE-ENTRY in place. *> Side effects: Updates merge variables and the temporary array. *> ----------------------------------------------------------------- MERGESORT. MOVE 1 TO MERGE-WIDTH PERFORM UNTIL MERGE-WIDTH >= VALUE-COUNT MOVE 1 TO MERGE-LEFT PERFORM UNTIL MERGE-LEFT > VALUE-COUNT COMPUTE MERGE-MID = MERGE-LEFT + MERGE-WIDTH - 1 IF MERGE-MID > VALUE-COUNT MOVE VALUE-COUNT TO MERGE-MID END-IF COMPUTE MERGE-RIGHT = MERGE-MID + MERGE-WIDTH IF MERGE-RIGHT > VALUE-COUNT MOVE VALUE-COUNT TO MERGE-RIGHT END-IF IF MERGE-MID < MERGE-RIGHT PERFORM THE-MERGE END-IF COMPUTE MERGE-LEFT = MERGE-LEFT + MERGE-WIDTH * 2 END-PERFORM MULTIPLY 2 BY MERGE-WIDTH END-PERFORM. END PROGRAM MERGE-SORT.