'**********************************************
'*   Demonstration program of Merge sorting   *
'*      (about n*log(n) comparisons used).    *
'* ------------------------------------------ *
'* Reference: "A book on C By Al Kelley and   *
'* Ira Pohl, The Benjamin/Cummings Publishing *
'* Company, Inc, 1984" [BIBLI 09].            *
'*                                            *
'*               Basic Version By J-P Moreau. *
'*                    (www.jpmoreau.fr)       *
'* ------------------------------------------ *
'* SAMPLE RUN:                                *
'*                                            *
'* Initial table A:                           *
'* 4 3 1 67 55 8 0 4 -5 37 7 4 2 9 1 -1       *
'*                                            *
'* Sorted table A:                            *
'* -5 -1 0 1 1 2 3 4 4 4 7 8 9 37 55 67       *
'*                                            *
'**********************************************
'Program Merge_Sorting
DEFINT I-N

MAXSIZE = 1024

DIM a(MAXSIZE), b(MAXSIZE), c(MAXSIZE), t(MAXSIZE), w(MAXSIZE)

  n = 16

  FOR i = 1 TO MAXSIZE
    t(i) = 0: w(i) = 0: a(i) = 0: b(i) = 0: c(i) = 0
  NEXT i

  t(1) = 4: t(2) = 3:  t(3) = 1: t(4) = 67
  t(5) = 55: t(6) = 8: t(7) = 0: t(8) = 4
  t(9) = -5: t(10) = 37: t(11) = 7: t(12) = 4
  t(13) = 2: t(14) = 9: t(15) = 1: t(16) = -1

  CLS
  PRINT
  PRINT " Initial table A:"
  FOR i = 1 TO n
    PRINT " "; t(i);
  NEXT
  PRINT

  GOSUB 2000  'call MergeSort(a,n,error)

  IF ierror = 0 THEN
    PRINT
    PRINT " Sorted table A:"
    FOR i = 1 TO n
      PRINT " "; t(i);
    NEXT
  END IF
  PRINT
  PRINT

END

' Merge Sorting of a() of size m1 and b() of size n1
' into c() of size m1+n1.
1000 i1 = 1: j1 = 1: k1 = 1
1010 if i1=k+1 or j1=k+1 then goto 1020
  IF a(i1) < b(j1) THEN
    c(k1) = a(i1)
    i1 = i1 + 1
  ELSE
    c(k1) = b(j1)
    j1 = j1 + 1
  END IF
  k1 = k1 + 1
GOTO 1010

'pick up any remainder
1020 if i1=k+1 then goto 1030
  c(k1) = a(i1)
  k1 = k1 + 1: i1 = i1 + 1
GOTO 1020
1030 if j1=k+1 then return
  c(k1) = b(j1)
  k1 = k1 + 1: j1 = j1 + 1
GOTO 1030
RETURN

' use function Merge() to sort an array key[] of size n
' In this version, n is a power of two.
2000 m = 1
  FOR m1 = 1 TO n - 1
    IF m < n THEN m = m * 2
  NEXT m1
  IF n = m AND n <= MAXSIZE THEN 'n is a power of two <= MAXSIZE
    k = 1
2020  j = 0
2030 FOR jj = 1 TO 2*k
      a(jj) = t(jj + j)
      b(jj) = t(jj + j + k)
    NEXT jj
    GOSUB 1000   'Merge(t(j+1),t(j+1+k),w(j+1),k,k)
    FOR jj = 1 to 2*k
      w(jj+j) = c(jj)
    NEXT jj
    j = j + 2 * k
    IF j < n - k THEN GOTO 2030
    k = k * 2
' put back w into a
    FOR j = 1 TO n
      t(j) = w(j)
    NEXT j
    IF k < n THEN GOTO 2020
  ELSE
    IF n <> m THEN
      PRINT " Error #1: size n of array not a power of 2!"
      ierror = 1
    END IF
    IF n > MAXSIZE THEN
      PRINT " Error #2: size of array is two bog!"
      ierror = 2
    END IF
  END IF
RETURN

'end of file merge.bas