'**********************************************************
'*   Demonstration Program of In-place Merge Sorting      *
'*  (about n * log(n) comparisons used with moderate      *
'*   extra storage).                                      *
'* ------------------------------------------------------ *
'* Reference: After a java algorithm By Jason Harrison,   *
'*            1995 University of British Columbia.        *
'*                                                        *
'*                   Basic Version By J-P Moreau, Paris.  *
'*                            (www.jpmoreau.fr)           *
'* ------------------------------------------------------ *
'* SAMPLE RUN:                                            *
'*                                                        *
'* Initial table A:                                       *
'*  4.00   3.00   1.00  67.00  55.00   8.00   0.00   4.00 *
'* -5.00  37.00   7.00   4.00   2.00   9.00   1.00  -1.00 *
'*                                                        *
'* Sorted table A:                                        *
'* -5.00  -1.00   0.00   1.00   1.00   2.00   3.00   4.00 *
'*  4.00   4.00   7.00   8.00   9.00  37.00  55.00  67.00 *
'*                                                        *
'**********************************************************
'Program MSORT
DEFDBL A-H, O-Z
DEFINT I-N

    n = 16
    n2 = n / 2
DIM A(n), tmp(n2)
DIM hi AS INTEGER
    
    A(1) = 4: A(2) = 3:  A(3) = 1: A(4) = 67
    A(5) = 55: A(6) = 8: A(7) = 0: A(8) = 4
    A(9) = -5: A(10) = 37: A(11) = 7: A(12) = 4
    A(13) = 2: A(14) = 9: A(15) = 1: A(16) = -1

    CLS
    PRINT
    PRINT " Initial table A:"
    FOR I = 1 TO n
      PRINT USING "####.##"; A(I);
      IF I = 8 THEN PRINT
    NEXT I

    lo = 1: hi = n
    GOSUB 2000 'call sort(A,1, n)

    PRINT
    PRINT
    PRINT " Sorted table A:"
    FOR I = 1 TO n
      PRINT USING "####.##"; A(I);
      IF I = 8 THEN PRINT
    NEXT I
    PRINT

END

'*****************************************************
'*  Sorts an array A of length N in ascending order  *
'*                by the Heapsort method             *
'* ------------------------------------------------- *
'* INPUTS:                                           *
'*          N1    size of table RA                   *
'*          A     table to be sorted                 *
'* OUTPUT:                                           *
'*          A     table sorted in ascending order    *
'*                                                   *
'* NOTE: The Heapsort method is a N Log N routine,   *
'*       and can be used for very large arrays.      *
'* ------------------------------------------------- *
'* REFERENCE:                                        *
'*  "NUMERICAL RECIPES by W.H. Press, B.P. Flannery, *
'*   S.A. Teukolsky and W.T. Vetterling, Cambridge   *
'*   University Press, 1986".                        *
'*****************************************************        
1000 'SUBROUTINE HPSORT(N1,A)
  L = n1 / 2 + 1
  IR = n1
  'The index L will be decremented from its initial value during the
  '"hiring" (heap creation) phase. Once it reaches 1, the index IR
  'will be decremented from its initial value down to 1 during the
  '"retirement-and-promotion" (heap selection) phase.
1010 IF L > 1 THEN
    L = L - 1
    RRA = A(L)
  ELSE
    RRA = A(IR)
    A(IR) = A(1)
    IR = IR - 1
    IF IR = 1 THEN
      A(1) = RRA
      RETURN
    END IF
  END IF
  I = L
  J = L + L
1020 IF J <= IR THEN
  IF J < IR THEN
    IF A(J) < A(J + 1) THEN J = J + 1
  END IF
  IF RRA < A(J) THEN
    A(I) = A(J)
    I = J: J = J + J
  ELSE
    J = IR + 1
  END IF
  GOTO 1020
  END IF
  A(I) = RRA
  GOTO 1010
RETURN

 '******************************************************
 '*  In-place sorting of a table a in ascending order  *
 '* -------------------------------------------------- *
 '* Inputs:                                            *
 '*         a :  Table of n real numbers               *
 '*         lo:  Starting index (>=0)                  *
 '*         hi:  Ending index (<=n-1), with lo<hi.     *
 '* Output:                                            *
 '*         a :  Table sorted in ascending order.      *
 '******************************************************
2000 'Subroutine sort(a, lo, hi)
DIM endlo AS INTEGER
DIM starthi AS INTEGER

  IF lo >= hi THEN RETURN  'no action 
  mid = (lo + hi) / 2

  'Partition the list into two lists and sort them with heapsort
  '(to avoid a recursive call of sort).
  n1 = mid
  GOSUB 1000 'call hpsort(mid,A)
  FOR I = lo TO mid
    tmp(I) = A(I)
    A(I) = A(mid + I)
  NEXT I
  GOSUB 1000 'call hpsort(mid,A(mid + 1))
  FOR I = lo TO mid
    A(mid + I) = A(I)
    A(I) = tmp(I)
  NEXT I

  'Merge the two sorted lists
  starthi = mid + 1
  endlo = mid
  WHILE lo <= endlo AND starthi <= hi
    IF A(lo) < A(starthi) THEN
      lo = lo + 1
    ELSE
    ' a(lo) >= a(starthi)
    ' The next element comes from the second list,
    ' move the a[starthi] element into the next
    ' position and shuffle all the other elements up.
      T = A(starthi)
      FOR k = starthi - 1 TO lo STEP -1
	A(k + 1) = A(k)
      NEXT k
      A(lo) = T
      lo = lo + 1
      endlo = endlo + 1
      starthi = starthi + 1
    END IF
  WEND

RETURN

'end of file msort.bas