C  THIS VERSION: 14/08/1991 AT 12:00:25 PM.
CS    SUBROUTINE SSORTA( N, A, INDA, LA, INDEX, INFORM )
CD    SUBROUTINE DSORTA( N, A, INDA, LA, INDEX, INFORM )
      INTEGER LA, N, INFORM
      LOGICAL INDEX
      INTEGER INDA( LA )
CS    REAL A( LA )
CD    DOUBLE PRECISION A( LA )
C
C  GIVEN AN ARRAY A, ELEMENTS A(1), ...., A(N), SUBROUTINE
C  SORTA REARRANGES THE ELEMENTS TO FORM A HEAP IN WHICH EACH PARENT
C  HAS A SMALLER VALUE THAN EITHER OF ITS CHILDREN.
C
C  ALGORITHM 232 OF CACM (J. W. J. WILLIAMS): A COMBINATION OF
C  ALGOL PROCEDURES SETHEAP AND INHEAP.
C  THIS VERSION BY NICK GOULD, 19/04/89.
C  FOR CGT PRODUCTIONS.
C
C  ------------------------- ARGUMENTS --------------------------
C
C  A      REAL ARRAY OF LENGTH LA. ON INPUT, A MUST CONTAIN THE
C         VALUES WHICH ARE TO BE SORTED. ON OUTPUT, THESE VALUES
C         WILL HAVE BEEN PERMUTED SO AS TO FORM A HEAP.
C
C  INDA   INTEGER ARRAY OF LENGTH LA. ON INPUT, INDA MAY BE USED
C         TO HOLD INDEXING INFORMATION (SUCH AS THE ORIGINAL ORDER
C         OF THE VALUES) ABOUT A. ON OUTPUT, INDA WILL HAVE BEEN
C         PERMUTED SO THAT INDA(K) STILL REFERS TO A(K). INDA IS
C         ONLY USED IF INDEX IS .TRUE.
C
C  LA     INTEGER, WHICH GIVES THE ACTUAL LENGTHS OF THE ARRAYS A
C         AND INDA. LA MUST BE AT LEAST N.
C
C  N      INTEGER, WHICH GIVES THE NUMBER OF VALUES TO BE SORTED.
C         N MUST BE POSITIVE.
C
C  INDEX  LOGICAL, WHICH MUST BE SET .TRUE. IF THE USER WISHES TO
C         USE THE INDEX ARRAY INDA, AND SET .FALSE. OTHERWISE.
C
C  INFORM INTEGER, WHICH INFORMS THE USER OF THE SUCCESS OF SORTA.
C
C         IF INFORM = 0 ON EXIT, THE HEAP HAS BEEN FORMED.
C         IF INFORM = 1 ON EXIT, N WAS INPUT WITH A VALUE LESS THAN
C                       OR EQUAL TO 0 AND THE HEAP HAS NOT BEEN FORMED.
C         IF INFORM = 2 ON EXIT, LA WAS INPUT WITH A VALUE LESS THAN N
C                       AND THE HEAP HAS NOT BEEN FORMED.
C
C  ------------------ END OF ARGUMENTS --------------------------
C
      INTEGER I, J, K, INDIN
CS    REAL RIN
CD    DOUBLE PRECISION RIN
C
C  ADD THE ELEMENTS TO THE HEAP ONE AT A TIME.
C
      IF ( N .LE. 0 ) THEN
         INFORM = 1
         RETURN
      END IF
      IF ( LA .LT. N ) THEN
         INFORM = 2
         RETURN
      END IF
      DO 20 K = 2, N
         RIN  = A( K )
         IF ( INDEX ) INDIN = INDA( K )
C
C  THE CYCLE MAY BE REPEATED LOG2(K) TIMES, BUT ON AVERAGE IS REPEATED
C  MERELY TWICE.
C
         I = K
   10    CONTINUE
         IF ( I .GT. 1 ) THEN
            J = I / 2
            IF ( A( J ) .GT. RIN ) THEN
               A( I ) = A( J )
               IF ( INDEX ) INDA( I ) = INDA( J )
               I = J
               GO TO 10
            END IF
         END IF
         A( I ) = RIN
         IF ( INDEX ) INDA( I ) = INDIN
   20 CONTINUE
      INFORM = 0
      RETURN
C
C  END OF SORTA.
C
      END
CS    SUBROUTINE SSORTB( M, A, INDA, LA, INDEX, INFORM )
CD    SUBROUTINE DSORTB( M, A, INDA, LA, INDEX, INFORM )
      INTEGER LA, M, INFORM
      LOGICAL INDEX
      INTEGER INDA( LA )
CS    REAL A( LA )
CD    DOUBLE PRECISION A( LA )
C
C  GIVEN AN ARRAY A, ELEMENTS A(1), ...., A(M) FORMING A HEAP,
C  SORTB ASSIGNS TO ROUT THE VALUE OF A(1), THE SMALLEST MEMBER OF
C  THE HEAP, AND ARRANGES THE REMAINING MEMBERS AS ELEMENTS 1 TO
C  M - 1 OF A. ROUT IS THEN PLACED IN A(M).
C
C  ALGORITHM 232 OF CACM (J. W. J. WILLIAMS): A COMBINATION OF
C  ALGOL PROCEDURES OUTHEAP AND SWOPHEAP.
C  THIS VERSION BY NICK GOULD, 19/04/89.
C  FOR CGT PRODUCTIONS.
C
C  ------------------------- ARGUMENTS --------------------------
C
C  M      INTEGER, WHICH GIVES THE NUMBER OF VALUES TO BE SORTED.
C         N MUST BE POSITIVE.
C
C  A      REAL ARRAY OF LENGTH LA. ON INPUT, A MUST CONTAIN THE
C         VALUES WHICH ARE TO BE SORTED STORED IN A HEAP.
C         ON OUTPUT, THESE VALUES, THE SMALLEST VALUE WILL HAVE
C         BEEN MOVED INTO A(M) AND THE REMAINING VALUES A(K),
C         K = 1,..., M-1 WILL HAVE BEEN RESTORED TO A HEAP.
C
C  INDA   INTEGER ARRAY OF LENGTH LA. ON INPUT, INDA MAY BE USED
C         TO HOLD INDEXING INFORMATION (SEE SORTA) ABOUT A.
C         ON OUTPUT, INDA WILL HAVE BEEN PERMUTED SO THAT INDA(K)
C         STILL REFERS TO A(K). INDA IS ONLY USED IF INDEX IS .TRUE.
C
C  LA     INTEGER, WHICH GIVES THE ACTUAL LENGTHS OF THE ARRAYS A
C         AND INDA. LA MUST BE AT LEAST M.
C
C  INDEX  LOGICAL, WHICH MUST BE SET .TRUE. IF THE USER WISHES TO
C         USE THE INDEX ARRAY INDA, AND SET .FALSE. OTHERWISE.
C         INDEX MUST NOT BE ALTERED BETWEEN CALLS TO SORTA AND
C         SUBSEQUENT CALLS TO SORTB.
C
C  INFORM INTEGER, WHICH INFORMS THE USER OF THE SUCCESS OF SORTB.
C
C         IF INFORM = 0 ON EXIT, THE SMALLEST VALUE HAS BEEN FOUND.
C         IF INFORM = 1 ON EXIT, M WAS INPUT WITH A VALUE LESS THAN
C                       OR EQUAL TO 0 AND THE HEAP HAS NOT BEEN FORMED.
C
C  ------------------ END OF ARGUMENTS --------------------------
C
      INTEGER I, J, INDIN, INDOUT
CS    REAL RIN, ROUT
CD    DOUBLE PRECISION RIN, ROUT
C
C  ADD THE ELEMENT RIN TO THE HEAP, EXTRACTS AND ASSIGN TO ROUT
C  THE VALUE OF THE SMALLEST MEMBER OF THE RESULTING SET, AND
C  LEAVE THE REMAINING ELEMENTS IN A HEAP OF THE ORIGINAL SIZE.
C  IN THIS PROCESS, ELEMENTS 1 TO N+1 OF THE ARRAY A MAY BE DISTURBED.
C
      IF ( M .LE. 0 ) THEN
         INFORM = 1
         RETURN
      END IF
      IF ( M .GT. 1 ) THEN
         I    = 1
         ROUT = A( 1 )
         IF ( INDEX ) INDOUT = INDA( 1 )
         RIN  = A( M )
         IF ( INDEX ) INDIN  = INDA( M )
C
C  MOVE FROM THE TOP OF THE HEAP COMPARING THE VALUE OF NODE I
C  WITH ITS TWO DAUGHTERS. IF NODE I IS SMALLEST, THE HEAP HAS BEEN
C  RESTORED. IF ONE OF THE CHILDREN IS SMALLEST, PROMOTE THIS CHILD
C  IN THE HEAP AND MOVE TO THE NOW VACATED NODE.
C  THIS CYCLE MAY BE REPEATED LOG2(M) TIMES.
C
   10    CONTINUE
         J = I + I
         IF ( J .LE. M - 1 ) THEN
C
C  DETERMINE WHICH OF THE TWO DAUGHTERS IS SMALLEST.
C
            IF ( A( J + 1 ) .LT. A( J ) ) J = J + 1
C
C  DETERMINE IF THE SMALLER DAUGHTER IS LESS THAN THE VALUE FROM NODE I.
C
            IF ( A( J ) .LT. RIN ) THEN
               A( I ) = A( J )
               IF ( INDEX ) INDA( I ) = INDA( J )
               I = J
               GO TO 10
            END IF
         END IF
C
C  THE HEAP HAS BEEN RESTORED.
C
         A( I ) = RIN
         IF ( INDEX ) INDA( I ) = INDIN
C
C  STORE THE SMALLEST VALUE IN THE NOW VACATED NTH POSITION OF THE LIST.
C
         A( M ) = ROUT
         IF ( INDEX ) INDA( M ) = INDOUT
      END IF
      INFORM = 0
      RETURN
C
C  END OF SORTB.
C
      END
