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
    * Purpose: read, sort, time, and save the input values.
    * Parameters: none.
    * Returns: no value; displays completion and elapsed time.
    * Variables: working-storage fields for values, count, and timing.
    * -------------------------------------------------------------------
       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
    * Purpose: heap-sort the loaded entries in place and capture start/end.
    * Parameters: none; uses VALUE-COUNT and THE-VALUES.
    * Returns: no value; updates entries and START-TIME/END-TIME.
    * Variables: ROOT, CHILD, TEMP, START-INDEX, END-INDEX, HEAP-SIZE.
    * -------------------------------------------------------------------
     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
    * Purpose: restore the max-heap property below ROOT.
    * Parameters: ROOT and HEAP-SIZE are the root and exclusive heap bound.
    * Returns: no value; mutates THE-VALUES.
    * Variables: CHILD selects the larger child; TEMP holds swap data.
    * -------------------------------------------------------------------
     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
    * Purpose: read numeric records from SORTING-INPUT into THE-VALUES.
    * Parameters: none; uses the SORTING-INPUT file assignment.
    * Returns: no value; updates VALUE-COUNT and END-OF-FILE.
    * Variables: INPUT-LINE - current input record.
    * -------------------------------------------------------------------
     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
    * Purpose: write the first VALUE-COUNT entries to SORTING-OUTPUT.
    * Parameters: none; uses THE-VALUES and VALUE-COUNT.
    * Returns: no value.
    * Variables: THE-INDEX - output array index; OUTPUT-LINE - formatted item.
    * -------------------------------------------------------------------
     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.