Simulated Recursion
by Earl Augusta

Listing One
 01  TABLE-TO-BE-SORTED.
     02 TABLE-ENTRY   PIC X(100) OCCURS 32000 TIMES.
*
 01  SWAP-ELEMENT     PIC X(100).
 01  PIVOT-VALUE      PIC X(100).
*
 01  WORKING-INDEXES.
     02 FURST         PIC 9(5) USAGE BINARY.
     02 LAAST         PIC 9(5) USAGE BINARY.
     02 PIVOT         PIC 9(5) USAGE BINARY.
     02 HOW-RETURN    PIC 9(5) USAGE BINARY.
*
 01  TABLE-OF-INDEXES.
     02 CURRENT-INDEXES OCCURS 100 TIMES.
         03 FILLER    PIC 9(5) USAGE BINARY.
         03 FILLER    PIC 9(5) USAGE BINARY.
         03 FILLER    PIC 9(5) USAGE BINARY.
         03 FILLER    PIC 9(5) USAGE BINARY.
 01  SESSION-INDEX    PIC 9(5) USAGE BINARY.
*
 01  LEFT-INDEX       PIC 9(5) USAGE BINARY.
 01  RIGHT-INDEX      PIC 9(5) USAGE BINARY.


Listing Two
 INITIALIZE-SORT.

     MOVE LOW-VALUES TO TABLE-OF-INDEXES.
     MOVE 1 TO FURST
               HOW-RETURN
               SESSION-INDEX.
     MOVE 32000 TO LAAST.
     MOVE WORKING-INDEXES TO
         CURRENT-INDEXES (SESSION-INDEX).


Listing Three
CALL-QUIKSORT.
     MOVE CURRENT-INDEXES (SESSION-INDEX) TO
         WORKING-INDEXES.
     IF HOW-RETURN = 2 GO TO DO-PIVOT-TO-LAST.
     IF HOW-RETURN = 3 GO TO SEE-IF-WE-ARE-ALL-DONE.
     IF FURST NOT < LAAST GO TO SEE-IF-WE-ARE-ALL-DONE.


Listing Four
 SPLIT-THE-LIST.
     MOVE TABLE-ENTRY (FURST) TO PIVOT-VALUE.
     MOVE FURST TO LEFT-INDEX.
     COMPUTE RIGHT-INDEX = LAAST + 1.
     PERFORM WITH TEST AFTER UNTIL
             RIGHT-INDEX <= LEFT-INDEX
         PERFORM WITH TEST AFTER UNTIL
             TABLE-ENTRY (LEFT-INDEX) >= PIVOT-VALUE
             ADD 1 TO LEFT-INDEX
         END-PERFORM
         PERFORM WITH TEST AFTER UNTIL
             TABLE-ENTRY (RIGHT-INDEX) <= PIVOT-VALUE
             SUBTRACT 1 FROM RIGHT-INDEX
         END-PERFORM
         IF LEFT-INDEX < RIGHT-INDEX
             PERFORM EXCHANGE-TWO-ELEMENTS
         END-IF
     END-PERFORM.
     MOVE FURST TO LEFT-INDEX.
 EXCHANGE-TWO-ELEMENTS.
     MOVE TABLE-ENTRY (LEFT-INDEX) TO ENTRY-HOLDER.
     MOVE TABLE-ENTRY (RIGHT-INDEX) TO
          TABLE-ENTRY (LEFT-INDEX).
     MOVE ENTRY-HOLDER TO TABLE-ENTRY (RIGHT-INDEX).
 EXCHANGE-TWO-ELEMENTS-EXIT.
     MOVE RIGHT-INDEX TO PIVOT.


Listing Five
 DO-FIRST-TO-PIVOT.
     MOVE 2 TO HOW-RETURN.
     MOVE WORKING-INDEXES TO
         CURRENT-INDEXES (SESSION-INDEX).
     COMPUTE LAAST = PIVOT - 1.
     MOVE 1 TO HOW-RETURN.
     ADD 1 TO SESSION-INDEX.
     MOVE WORKING-INDEXES TO 
         CURRENT-INDEXES (SESSION-INDEX).
     GO TO CALL-QUIKSORT.

*
 DO-PIVOT-TO-LAST.
     MOVE 3 TO HOW-RETURN.
     MOVE WORKING-INDEXES TO 
         CURRENT-INDEXES (SESSION-INDEX).
     COMPUTE FURST = PIVOT + 1.
     MOVE 1 TO HOW-RETURN.
     ADD 1 TO SESSION-INDEX.
     MOVE WORKING-INDEXES TO
         CURRENT-INDEXES (SESSION-INDEX).
     GO TO CALL-QUIKSORT.


Listing Six
*
 SEE-IF-WE-ARE-ALL-DONE.
     SUBTRACT 1 FROM SESSION-INDEX.
     IF SESSION-INDEX > 0
         GO TO CALL-QUIKSORT.
     STOP RUN.


1