# hpsort.f

          SUBROUTINE HPSORT (HX, N, STRBEG, STREND, IPERM, KFLAG, WORK, IER)
    C***BEGIN PROLOGUE  HPSORT
    C***PURPOSE  Return the permutation vector generated by sorting a
    C            substring within a character array and, optionally,
    C            rearrange the elements of the array.  The array may be
    C            sorted in forward or reverse lexicographical order.  A
    C            slightly modified quicksort algorithm is used.
    C***LIBRARY   SLATEC
    C***CATEGORY  N6A1C, N6A2C
    C***TYPE      CHARACTER (SPSORT-S, DPSORT-D, IPSORT-I, HPSORT-H)
    C***KEYWORDS  PASSIVE SORTING, SINGLETON QUICKSORT, SORT, STRING SORTING
    C***AUTHOR  Jones, R. E., (SNLA)
    C           Rhoads, G. S., (NBS)
    C           Sullivan, F. E., (NBS)
    C           Wisniewski, J. A., (SNLA)
    C***DESCRIPTION
    C
    C   HPSORT returns the permutation vector IPERM generated by sorting
    C   the substrings beginning with the character STRBEG and ending with
    C   the character STREND within the strings in array HX and, optionally,
    C   rearranges the strings in HX.   HX may be sorted in increasing or
    C   decreasing lexicographical order.  A slightly modified quicksort
    C   algorithm is used.
    C
    C   IPERM is such that HX(IPERM(I)) is the Ith value in the
    C   rearrangement of HX.  IPERM may be applied to another array by
    C   calling IPPERM, SPPERM, DPPERM or HPPERM.
    C
    C   An active sort of numerical data is expected to execute somewhat
    C   more quickly than a passive sort because there is no need to use
    C   indirect references. But for the character data in HPSORT, integers
    C   in the IPERM vector are manipulated rather than the strings in HX.
    C   Moving integers may be enough faster than moving character strings
    C   to more than offset the penalty of indirect referencing.
    C
    C   Description of Parameters
    C      HX - input/output -- array of type character to be sorted.
    C           For example, to sort a 80 element array of names,
    C           each of length 6, declare HX as character HX(100)*6.
    C           If ABS(KFLAG) = 2, then the values in HX will be
    C           rearranged on output; otherwise, they are unchanged.
    C      N  - input -- number of values in array HX to be sorted.
    C      STRBEG - input -- the index of the initial character in
    C               the string HX that is to be sorted.
    C      STREND - input -- the index of the final character in
    C               the string HX that is to be sorted.
    C      IPERM - output -- permutation array such that IPERM(I) is the
    C              index of the string in the original order of the
    C              HX array that is in the Ith location in the sorted
    C              order.
    C      KFLAG - input -- control parameter:
    C            =  2  means return the permutation vector resulting from
    C                  sorting HX in lexicographical order and sort HX also.
    C            =  1  means return the permutation vector resulting from
    C                  sorting HX in lexicographical order and do not sort
    C                  HX.
    C            = -1  means return the permutation vector resulting from
    C                  sorting HX in reverse lexicographical order and do
    C                  not sort HX.
    C            = -2  means return the permutation vector resulting from
    C                  sorting HX in reverse lexicographical order and sort
    C                  HX also.
    C      WORK - character variable which must have a length specification
    C             at least as great as that of HX.
    C      IER - output -- error indicator:
    C          =  0  if no error,
    C          =  1  if N is zero or negative,
    C          =  2  if KFLAG is not 2, 1, -1, or -2,
    C          =  3  if work array is not long enough,
    C          =  4  if string beginning is beyond its end,
    C          =  5  if string beginning is out-of-range,
    C          =  6  if string end is out-of-range.
    C
    C     E X A M P L E  O F  U S E
    C
    C      CHARACTER*2 HX, W
    C      INTEGER STRBEG, STREND
    C      DIMENSION HX(10), IPERM(10)
    C      DATA (HX(I),I=1,10)/ '05','I ',' I','  ','Rs','9R','R9','89',
    C     1     ',*','N"'/
    C      DATA STRBEG, STREND / 1, 2 /
    C      CALL HPSORT (HX,10,STRBEG,STREND,IPERM,1,W)
    C      PRINT 100, (HX(IPERM(I)),I=1,10)
    C 100 FORMAT (2X, A2)
    C      STOP
    C      END
    C
    C***REFERENCES  R. C. Singleton, Algorithm 347, An efficient algorithm
    C                 for sorting with minimal storage, Communications of
    C                 the ACM, 12, 3 (1969), pp. 185-187.
    C***ROUTINES CALLED  XERMSG
    C***REVISION HISTORY  (YYMMDD)
    C   761101  DATE WRITTEN
    C   761118  Modified by John A. Wisniewski to use the Singleton
    C           quicksort algorithm.
    C   811001  Modified by Francis Sullivan for string data.
    C   850326  Documentation slightly modified by D. Kahaner.
    C   870423  Modified by Gregory S. Rhoads for passive sorting with the
    C           option for the rearrangement of the original data.
    C   890620  Algorithm for rearranging the data vector corrected by R.
    C           Boisvert.
    C   890622  Prologue upgraded to Version 4.0 style by D. Lozier.
    C   920507  Modified by M. McClain to revise prologue text.
    C   920818  Declarations section rebuilt and code restructured to use
    C           IF-THEN-ELSE-ENDIF.  (SMR, WRB)
    C***END PROLOGUE  HPSORT