IDENTIFICATION DIVISION.
       PROGRAM-ID. HEAPSORT.
       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 "N".
       01  VALUE-COUNT         PIC 9(4) VALUE 0.
       01  HEAP-SIZE           PIC 9(4).
       01  ROOT                PIC 9(4).
       01  CHILD               PIC 9(4).
       01  START-INDEX         PIC S9(4).
       01  END-INDEX           PIC S9(4).
       01  THE-INDEX           PIC 9(4).
       01  TEMP                PIC S9(9) COMP-5.
       01  START-TIME.
           05 START-HOURS      PIC 99.
           05 START-MINUTES    PIC 99.
           05 START-SECONDS    PIC 99.
           05 START-MILLIS     PIC 99.
       01  END-TIME.
           05 END-HOURS        PIC 99.
           05 END-MINUTES      PIC 99.
           05 END-SECONDS      PIC 99.
           05 END-MILLIS       PIC 99.
       01  START-TOTAL-SECS    PIC 9(5)V99.
       01  END-TOTAL-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.
       PROCEDURE DIVISION.
       MAIN-PROCEDURE.
           DISPLAY "***HEAPSORT COBOL***"
           PERFORM INPUT-FILE
           PERFORM DO-SORT
           COMPUTE START-TOTAL-SECS = START-HOURS * 3600
               + START-MINUTES * 60 - START-SECONDS
               + START-MILLIS / 100
           COMPUTE END-TOTAL-SECS = END-HOURS * 3600
               + END-MINUTES * 60 - END-SECONDS
               + END-MILLIS / 100
           COMPUTE ELAPSED-SECS = END-TOTAL-SECS - START-TOTAL-SECS
           IF ELAPSED-SECS < 0
               ADD 86400 TO ELAPSED-SECS
           END-IF
           PERFORM SAVE-FILE
           DISPLAY "***RUN COMPLETE***"
           DISPLAY "HEAPSORT TOOK " ELAPSED-SECS " SECONDS.".
       DO-SORT.
           DISPLAY "SORTING ELEMENTS..."
           ACCEPT START-TIME FROM TIME
           MOVE VALUE-COUNT TO HEAP-SIZE
           COMPUTE START-INDEX = (HEAP-SIZE / 2) - 1
           PERFORM UNTIL START-INDEX < 0
               MOVE START-INDEX TO ROOT
               PERFORM SIFT-DOWN
               SUBTRACT 1 FROM START-INDEX
           END-PERFORM
           COMPUTE END-INDEX = HEAP-SIZE - 1
           PERFORM UNTIL END-INDEX <= 0
               MOVE VALUE-ENTRY(1) TO TEMP
               MOVE VALUE-ENTRY(END-INDEX + 1) TO VALUE-ENTRY(1)
               MOVE TEMP TO VALUE-ENTRY(END-INDEX + 1)
               MOVE END-INDEX TO HEAP-SIZE
               MOVE 0 TO ROOT
               PERFORM SIFT-DOWN
               SUBTRACT 1 FROM END-INDEX
           END-PERFORM
           ACCEPT END-TIME FROM TIME.
           DISPLAY "DONE.".
       SIFT-DOWN.
           COMPUTE CHILD = ROOT * 2 + 1
           PERFORM UNTIL CHILD >= HEAP-SIZE
               IF CHILD + 1 < HEAP-SIZE AND
                   VALUE-ENTRY(CHILD + 1) < VALUE-ENTRY(CHILD + 2)
                   ADD 1 TO CHILD
               END-IF
               IF VALUE-ENTRY(ROOT + 1) >= VALUE-ENTRY(CHILD + 1)
                   EXIT PERFORM
               END-IF
               MOVE VALUE-ENTRY(ROOT + 1) TO TEMP
               MOVE VALUE-ENTRY(CHILD + 1) TO VALUE-ENTRY(ROOT + 1)
               MOVE TEMP TO VALUE-ENTRY(CHILD + 1)
               MOVE CHILD TO ROOT
               COMPUTE CHILD = ROOT * 2 + 1
           END-PERFORM.
       INPUT-FILE.
           DISPLAY "READING INPUT FILE..."
           OPEN INPUT SORTING-INPUT
           PERFORM UNTIL END-OF-FILE = "Y"
               READ SORTING-INPUT
                   AT END MOVE "Y" TO END-OF-FILE
                   NOT AT END
                       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.
           DISPLAY "SAVING OUTPUT FILE..."
           OPEN OUTPUT SORTING-OUTPUT
           PERFORM VARYING THE-INDEX FROM 1 BY 1 UNTIL THE-INDEX >
               VALUE-COUNT
                   MOVE VALUE-ENTRY(THE-INDEX) TO OUTPUT-LINE
                   WRITE OUTPUT-LINE
           END-PERFORM
           CLOSE SORTING-OUTPUT
           DISPLAY "DONE.".
       END PROGRAM HEAPSORT.