SUBROUTINE SPN(K, L, II, JJ, MIN)                                 SPN   10
C         **SAMPLE SEARCH SORT**
C A LIST INSERTION SORT TO BUILD UP A SINGLE CIRCULARLY
C LINKED LIST.
C THIS ALGORITHM SORTS THE KEYS K(II),K(II+1),...,K(JJ) IN
C ASCENDING SORTING ORDER BY THE MEANS OF THE POINTER FIELDS
C L(II),L(II+1),....,L(JJ).
C THE EXPECTED NUMBER OF NECESSARY COMPARISIONS AND
C ACCESSES IS OF ORDER N**1.5 (N=JJ-II+1).
C WITH SINGLE KEYS THE ALGORITHM IS PROPORTIONAL IN SORTING
C TIME TO A SHELL SORT ALGORITHM.
C ISTRT  AUXILIARY VARIABLE IN RANDOM SEARCH
C K      ARRAY OF N KEYS.
C L      ARRAY FOR N POINTERS.
C IPOI   VARIABLE WHICH IS USED TO MANIPULATE POINTERS.
C KDIFF  DISTANCE OF THE KEY FOUND IN RANDOM SEARCH
C            AND THE KEY WHICH SHALL BE INSERTED.
C KEY,MADIN  ADDRESSES USED IN SEQUENTIAL AND RANDOM SEARCH.
C MAX,MIN    VARIABLES TO STORE THE ADDRESS OF THE
C            KEYS WITH THE SMALLEST AND LARGEST VALUE.
C N      NUMBER OF KEYS.
C IRT    STEP WIDTH IN RANDOM SEARCH.
C TAB    ARRAY OF VALUES WHICH DETERMINES THE SAMPLE SIZE.
C THE ALGORITHM IS STABLE.
C MIN RETURNS THE ADDRESS OF THE FIRST RECORD IN SORTING
C ORDER OF THE LIST.
      INTEGER TAB(57)
      DIMENSION K(1), L(1)
      DATA TAB(1), TAB(2), TAB(3), TAB(4), TAB(5), TAB(6), TAB(7),
     * TAB(8), TAB(9), TAB(10), TAB(11), TAB(12), TAB(13), TAB(14),
     * TAB(15), TAB(16), TAB(17), TAB(18), TAB(19), TAB(20),
     * TAB(21), TAB(22), TAB(23), TAB(24), TAB(25), TAB(26),
     * TAB(27), TAB(28), TAB(29), TAB(30), TAB(31), TAB(32),
     * TAB(33), TAB(34), TAB(35), TAB(36), TAB(37), TAB(38),
     * TAB(39), TAB(40), TAB(41), TAB(42), TAB(43), TAB(44),
     * TAB(45), TAB(46), TAB(47), TAB(48), TAB(49), TAB(50),
     * TAB(51), TAB(52), TAB(53), TAB(54), TAB(55), TAB(56),
     * TAB(57) /3,5,10,17,26,37,50,65,82,101,122,145,170,197,226,
     * 257,290,325,362,401,442,485,530,577,626,677,730,785,842,901,
     * 962,1025,1090,1157,1226,1297,1370,1445,1522,1601,1682,1765,
     * 1850,1937,2026,2117,2210,2305,2402,2501,2602,2705,2810,2917,
     * 3026,3137,3250/
C  INITIALISATION (PART I)
C -----------------------------------------------------------
      MIN = II
      MAX = II
      L(II) = II
      IF (JJ-II) 170, 170, 10
   10 KMIN = K(MIN)
      KMAX = KMIN
      IA = II + 1
      IRT = 1
      ITAB = TAB(1) + II - 1
      ISTRT = II
C -----------------------------------------------------------
C  INSERTION LOOP (PART II)
      DO 160 J=IA,JJ
C CORRECTION OF THE SAMPLE SIZE (IF NECESSARY)
        IF (J-ITAB) 30, 20, 20
C -----------------------------------------------------------
   20   IRT = IRT + 1
        ISTRT = ISTRT + 1
        ITAB = TAB(IRT) + II - 1
C -----------------------------------------------------------
   30   KJ = K(J)
C PROVISION FOR ARISING LARGEST AND SMALLEST KEYS (1).
        IF (KJ-KMAX) 40, 60, 60
C -----------------------------------------------------------
   40   IF (KJ-KMIN) 70, 50, 90
C -----------------------------------------------------------
C  KEY WHICH SHALL BE INSERTED IS EQUAL TO THE MINIMAL
C  KEY SORTED SO FAR (2).
C -----------------------------------------------------------
   50   MADIN = MIN
        MIN = J
        GO TO 130
C -----------------------------------------------------------
C  KEY WHICH SHALL BE INSERTED IS EQUAL TO OR LARGER THAN THE
C  MAXIMAL KEY SORTED SO FAR (3).
C -----------------------------------------------------------
   60   I = MAX
        MAX = J
        KMAX = K(J)
        GO TO 80
C -----------------------------------------------------------
C  KEY FOR INSERTION IS SMALLER THAN THE SMALLEST KEY SORTED
C  SO FAR (4).
C -----------------------------------------------------------
   70   I = MAX
        MIN = J
        KMIN = K(J)
C -----------------------------------------------------------
C  INSERTION OF THE RECORD AND CORRECTION OF THE VALUE WHICH
C  DETERMINES THE SAMPLE SIZE (5).
C -----------------------------------------------------------
   80   IPOI = L(I)
        L(I) = J
        L(J) = IPOI
        GO TO 160
C -----------------------------------------------------------
C  INITIALISATION FOR RANDOM SEARCH (FIRST STEP) (6).
C -----------------------------------------------------------
   90   MADIN = MIN
        IPOI = J - 1
        I = KJ - KMIN
C -----------------------------------------------------------
C  RANDOM SEARCH (7).
C  PART 1 (7A).
C -----------------------------------------------------------
        DO 120 KEY=ISTRT,IPOI,IRT
          KDIFF = KJ - K(KEY)
          IF (KDIFF) 120, 140, 100
C -----------------------------------------------------------
  100     IF (I-KDIFF) 120, 120, 110
C -----------------------------------------------------------
C  PART 2.. STORE NEAREST KEY FOUND SO FAR (7B)
C -----------------------------------------------------------
  110     I = KDIFF
          MADIN = KEY
C -----------------------------------------------------------
  120   CONTINUE
C -----------------------------------------------------------
C  SEQUENTIAL SEARCH (8).
C -----------------------------------------------------------
  130   IPOI = MADIN
        MADIN = L(IPOI)
        IF (KJ-K(MADIN)) 150, 130, 130
C -----------------------------------------------------------
C  KEY SEARCHED FOR WAS FOUND IN RANDOM SEARCH
C -----------------------------------------------------------
  140   MADIN = KEY
        GO TO 130
C -----------------------------------------------------------
C  INSERT (9)
C -----------------------------------------------------------
  150   L(IPOI) = J
        L(J) = MADIN
C -----------------------------------------------------------
  160 CONTINUE
C -----------------------------------------------------------
  170 MIN = L(MAX)
      L(MAX) = 0
      RETURN
      END