Quite BASIC -- Merge Sort

Output

Canvas

BASIC Program

REM Quite BASIC Algorithm Project
REM Merge Sort program

REM Initialize the arrays
LET N = 10
LET C = 0 
ARRAY A
ARRAY B
GOSUB 3000
REM Print the random array
PRINT "Random list:"
GOSUB 4000
REM Sort the array
GOSUB 2000
PRINT "Sorted list:"
REM Print the sorted array
GOSUB 4000
PRINT "Number of Iterations: ";
PRINT C
END

REM Merge sort the list A of length N
REM Using the array B for temporary storage
REM 
REM === Split phase ===
REM C counts the number of split/merge iterations
LET C = C + 1
LET X = 1
LET Y = 1
LET Z = N
GOTO 2110
IF A[X] < A[X-1] THEN GOTO 2170
LET B[Y] = A[X]
LET Y = Y + 1
LET X = X + 1 
IF Z < Y THEN GOTO 2200
GOTO 2100
IF A[X] < A[X-1] THEN GOTO 2110
LET B[Z] = A[X]
LET Z = Z - 1
LET X = X + 1 
IF Z < Y THEN GOTO 2300
GOTO 2160
REM 
REM === Merge Phase ===
REM Q means "we're done" (or "quit")
REM Q is 1 until we know that this is _not_ the last iteration
LET Q = 1
LET X = 1
LET Y = 1
LET Z = N
REM First select the smaller item
IF B[Y] < B[Z] THEN GOTO 2480 ELSE GOTO 2520
REM Check if the loop is done
IF Z < Y THEN GOTO 2560
REM If both items are smaller then start over with the smallest
IF B[Y] >= A[X-1] OR B[Z] >= A[X-1] THEN GOTO 2450
LET Q = 0
GOTO 2370
REM Pick the smallest item that represents an increase
IF B[Z] < B[Y] AND B[Z] >= A[X-1] THEN GOTO 2520
IF B[Z] > B[Y] AND B[Y] < A[X-1] THEN GOTO 2520
LET A[X] = B[Y]
LET Y = Y + 1
LET X = X + 1
GOTO 2390
LET A[X] = B[Z]
LET Z = Z - 1
LET X = X + 1
GOTO 2390
IF Q = 0 THEN GOTO 2030
RETURN

REM Create a random list of N integers
FOR I = 1 TO N
LET A[I] = FLOOR(RAND(100))
NEXT I
RETURN 

REM PRINT the list A
FOR I = 1 TO N
PRINT A[I];
PRINT ", ";
NEXT I
PRINT
RETURN
      
  

Controls

Line:

Expr:

Value:

>QUITE BASIC
>

fun and learning for smart kids

nostalgia for the rest of us

>QUITE BASIC>

fun and learning for smart kids

nostalgia for the rest of us

>QUITE BASIC
>