Algorithm Alley
by Karl-Dietrich Neubert

Listing One
      SUBROUTINE FLASH1 (A. N. L. M)
C     SORTS ARRY A WITH N ELEMENTS BY USE OF INDEX VECTOR L 
C     OF DIMENSION M WITH M ABOUT 0.1 N. 
C     COPYRIGHT (C)  K. - D. NEUBERT  1997                           

      DIMENSION A(1),L(1)
C     ============================ CLASS FORMATION ===== 
      ANMIN=A(1)
      NMAX=1 
      DO I=1,N
         IF( A(I).LT.ANMIN) ANMIN=A(I)
         IF( A(I).GT.A(NMAX)) NMAX=I
      END DO
      IF (ANMIN.EQ.A(NMAX)) RETURN
      C1=(M - 1) / (A(NMAX) - ANMIN))
      DO K=1,M  
         L(K)=0
      END DO 
      DO I=1,N
         K=1 + INT(C1 * (A(I) - ANMIN))
         L(K)=L(K) + 1
      END DO
      DO K=2,M
         L(K)=L(K) + L(K - 1)
      END DO
      HOLD=A(NMAX)
      A(NMAX)=A(1) 
      A(1)=HOLD
C     =============================== PERMUTATION ===== 
      NMOVE=0 
      J=1
      K=M
      DO WHILE (NMOVE.LT.N - 1)
         DO WHILE (J.GT.L(K)) 
            J=J + 1 
            K=1 + INT(C1 * (A(J) - ANMIN)) 
         END DO  
         FLASH=A(J)
         DO WHILE (.NOT.(J.EQ.L(K) + 1)) 
            K=1 + INT(C1 * (FLASH - ANMIN))
            HOLD=A(L(K)) 
            A(L(K))=FLASH
            FLASH=HOLD
            L(K)=L(K) - 1
            NMOVE=NMOVE + 1 
         END DO
      END DO
C     ========================= STRAIGHT INSERTION =====
      DO I=N-2,1,-1
         IF  (A(I + 1).LT.A(I)) THEN
            HOLD=A(I)
            J=I
            DO WHILE  (A(J + 1).LT.HOLD)
               A(J)=A(J + 1) 
               J=J + 1 
            END DO
            A(J)=HOLD 
         ENDIF
      END DO
C     =========================== RETURN,END FLASH1 =====
      RETURN
      END  



