      SUBROUTINE SORT( X, N )

C     Does an insertion sort on a vector of real numbers

C     At the Ith step, the first I-1 positions contain a sorted
C     vector.  We shall insert the Ith value into its place in that
C     vector shifting up to produce a new vector of length I.

      REAL X( * )

      IF ( N .EQ. 1 ) RETURN

      DO 2000 I = 2, N

         T = X( I )

         IF ( T .LT. X( 1 ) ) THEN
C           ------ Goes in the first position
            CALL SHIFTIN( X, T, 1, I - 1 )

         ELSE IF ( T .LT. X( I - 1 ) ) THEN

C           *** Binary search for its place ***

            IRIGHT = I - 1
            ILEFT  = 1

 1000       IMID = ( ILEFT + IRIGHT ) / 2

            IF ( T .LT. X(IMID) ) THEN
               IRIGHT = IMID
            ELSE
               ILEFT  = IMID
            ENDIF

            IF ( IRIGHT .GT. ILEFT + 1 ) GOTO 1000

C           ------ Shift and insert
            CALL SHIFTIN( X, T, IRIGHT, I - 1 )

         ENDIF

 2000 CONTINUE

      RETURN
      END

      SUBROUTINE SHIFTIN( X, T, I1, I2 )

C     Shift values (I1, I2) one position to the right
C     and insert T at position I1

      REAL X( * )

      DO 1000 K = I2, I1, -1
         X( K + 1 ) = X( K )
 1000 CONTINUE

      X( I1 ) = T

      RETURN
      END
