'********************************************** '* 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