10 GRAPHICS 0 20 MAXVALS=1000:DIM VALUES(MAXVALS):COUNT=0 30 DIM LEFTVALUES(MAXVALS/2+1),RIGHTVALUES(MAXVALS/2+1) 40 DIM LOWSTACK(32),HIGHSTACK(32),MIDSTACK(32):STACKPTR=0 50 DIM INFILE$(11), OUTFILE$(12) 60 INFILE$="D:INPUT.TXT":OUTFILE$="D:OUTPUT.TXT" 70 PRINT "=====MERGESORT ATARI BASIC======" 80 GOSUB 1000 90 TIMESTART=PEEK(18)*65536+PEEK(19)*256+PEEK(20) 100 STACKPTR=0:LOWINDEX=0:HIGHINDEX=COUNT-1:GOSUB 4000 110 ELAPSED=INT((PEEK(18)*65536+PEEK(19)*256+PEEK(20)-TIMESTART)/60) 120 GOSUB 2000 130 PRINT "==========RUN COMPLETE==========" 140 PRINT "MERGESORT TOOK ";ELAPSED;" SECONDS." 150 PRINT "===============================" 999 END 1000 REM ------------------------------------------------------------------- 1001 REM load_file 1002 REM Purpose: Read integer records from INFILE$ into VALUES and update COUNT. 1003 REM Parameters: INFILE$ is the input path; COUNT and VALUES are shared state. 1004 REM Returns: No value; fills VALUES and sets COUNT to the number read. 1005 REM Side effects: Opens and closes the input file and prints progress. 1006 REM ------------------------------------------------------------------- 1007 REM ==LOAD INPUT FILE== 1010 PRINT "READING INPUT FILE..."; 1020 DIM L$(80) 1030 OPEN #1,4,0,INFILE$ 1040 TRAP 1100 1050 INPUT #1,L$ 1060 IF L$="" THEN GOTO 1040 1070 VALUES(COUNT)=VAL(L$) 1080 COUNT=COUNT+1 1090 GOTO 1040 1100 CLOSE #1 1110 TRAP 65535 1120 PRINT "DONE." 1130 RETURN 2000 REM ------------------------------------------------------------------- 2001 REM save_file 2002 REM Purpose: Write VALUES(0) through VALUES(COUNT-1) to OUTFILE$. 2003 REM Parameters: OUTFILE$ is the output path; COUNT and VALUES are shared state. 2004 REM Returns: No value; creates the output file and writes one value per line. 2005 REM Side effects: Opens and closes the output file and prints progress. 2006 REM ------------------------------------------------------------------- 2007 REM ==SAVE OUTPUT FILE== 2010 PRINT "WRITING OUTPUT FILE..."; 2020 OPEN #1, 8,0,OUTFILE$ 2030 FOR I = 0 TO COUNT-1 2040 PRINT #1, VALUES(I) 2050 NEXT I 2060 CLOSE #1 2070 PRINT "DONE." 2080 RETURN 3000 REM ------------------------------------------------------------------- 3001 REM merge 3002 REM Purpose: Merge VALUES(LOWINDEX..MIDINDEX) and VALUES(MIDINDEX+1..HIGHINDEX). 3003 REM Parameters: LOWINDEX, MIDINDEX, HIGHINDEX and the arrays are shared state. 3004 REM Returns: No value; replaces the selected range in VALUES with sorted values. 3005 REM Side effects: Copies values into temporary arrays and overwrites VALUES. 3006 REM ------------------------------------------------------------------- 3007 REM ==MERGE=== 3010 LEFTCOUNT=MIDINDEX-LOWINDEX+1 3020 RIGHTCOUNT=HIGHINDEX-MIDINDEX 3030 REM -- COPY LEFT HALF 3040 FOR COPYPOS=0 TO LEFTCOUNT-1 3050 LEFTVALUES(COPYPOS)=VALUES(LOWINDEX+COPYPOS) 3060 NEXT COPYPOS 3070 REM -- COPY RIGHT HALF 3080 FOR COPYPOS=0 TO RIGHTCOUNT-1 3090 RIGHTVALUES(COPYPOS)=VALUES(MIDINDEX+1+COPYPOS) 3100 NEXT COPYPOS 3110 LEFTPOS=0 3120 RIGHTPOS=0 3130 MERGEPOS=LOWINDEX 3200 REM -- MERGE WHILE BOTH HALVES HAVE VALUES 3210 IF LEFTPOS>=LEFTCOUNT THEN GOTO 3300 3220 IF RIGHTPOS>=RIGHTCOUNT THEN GOTO 3300 3230 IF LEFTVALUES(LEFTPOS)<=RIGHTVALUES(RIGHTPOS) THEN GOTO 3270 3240 VALUES(MERGEPOS)=RIGHTVALUES(RIGHTPOS) 3250 RIGHTPOS=RIGHTPOS+1 3260 GOTO 3290 3270 VALUES(MERGEPOS)=LEFTVALUES(LEFTPOS) 3280 LEFTPOS=LEFTPOS+1 3290 MERGEPOS=MERGEPOS+1 3295 GOTO 3210 3300 REM -- COPY REMAINING LEFT VALUES 3310 IF LEFTPOS>=LEFTCOUNT THEN GOTO 3400 3320 VALUES(MERGEPOS)=LEFTVALUES(LEFTPOS) 3330 LEFTPOS=LEFTPOS+1 3340 MERGEPOS=MERGEPOS+1 3350 GOTO 3310 3400 REM -- COPY REMAINING RIGHT VALUES 3410 IF RIGHTPOS>=RIGHTCOUNT THEN RETURN 3420 VALUES(MERGEPOS)=RIGHTVALUES(RIGHTPOS) 3430 RIGHTPOS=RIGHTPOS+1 3440 MERGEPOS=MERGEPOS+1 3450 GOTO 3410 4000 REM ------------------------------------------------------------------- 4001 REM mergesort 4002 REM Purpose: Recursively divide the range, sort both halves, then merge them. 4003 REM Parameters: LOWINDEX and HIGHINDEX are the inclusive range bounds. 4004 REM Returns: No value; sorts that range of VALUES in place. 4005 REM Side effects: Saves recursive bounds on the LOW/HIGH/MID stacks. 4006 REM ------------------------------------------------------------------- 4007 REM ==MERGESORT== 4010 IF LOWINDEX>=HIGHINDEX THEN RETURN 4020 MIDINDEX=INT((LOWINDEX+HIGHINDEX)/2) 4100 REM -- PUSH CURRENT RANGE 4110 STACKPTR=STACKPTR+1 4120 LOWSTACK(STACKPTR)=LOWINDEX 4130 HIGHSTACK(STACKPTR)=HIGHINDEX 4140 MIDSTACK(STACKPTR)=MIDINDEX 4200 REM -- SORT LEFT HALF 4210 HIGHINDEX=MIDINDEX 4220 GOSUB 4000 4230 LOWINDEX=LOWSTACK(STACKPTR) 4240 HIGHINDEX=HIGHSTACK(STACKPTR) 4250 MIDINDEX=MIDSTACK(STACKPTR) 4300 REM -- SORT RIGHT HALF 4310 LOWINDEX=MIDINDEX+1 4320 GOSUB 4000 4330 LOWINDEX=LOWSTACK(STACKPTR) 4340 HIGHINDEX=HIGHSTACK(STACKPTR) 4350 MIDINDEX=MIDSTACK(STACKPTR) 4400 REM -- POP RANGE AND MERGE 4410 STACKPTR=STACKPTR-1 4420 GOSUB 3000 4430 RETURN 4999 REM =============