DECLARE SUB sort (x1!, x2!)
DECLARE SUB check ()
DECLARE SUB di (r1!, r2!, c!)
DECLARE SUB disp ()
DIM SHARED siz
siz = 15000
DIM SHARED arr(1 TO siz)
DIM SHARED mark(1 TO siz)
DIM SHARED bck(1 TO siz)
DIM SHARED dbg
WIDTH 80, 50

dbg = 1
CLS
FOR i = 1 TO 1000
LOCATE 5, 40
PRINT i
RANDOMIZE i
siz = 45

FOR a = 1 TO siz
  arr(a) = INT(RND * 100)
  bck(a) = arr(a)
NEXT a
11

sort 1, siz
disp


fail = 0
FOR i2 = 1 TO siz - 1
  IF arr(i2) > arr(i2 + 1) THEN
    PRINT "wrong!"
    a$ = INPUT$(1)
    fail = 1
    GOTO 10
  END IF
NEXT i2
10

IF fail = 1 THEN
  FOR i2 = 1 TO siz
    arr(i2) = bck(i2)
  NEXT i2
  dbg = 1
  GOTO 11
END IF

NEXT i

SUB di (r1, r2, c)

mark(r1) = c
mark(r2) = c
disp
mark(r1) = 0
mark(r2) = 0


END SUB

SUB disp
FOR i = 1 TO siz
  LOCATE i, 1
  COLOR 15, mark(i)
  PRINT arr(i), "    ", i
NEXT i

IF dbg = 1 THEN a$ = INPUT$(1)
'SOUND 0, .05
END SUB

SUB sort (x1, x2)
min = 99999
max = -99999
FOR i = x1 TO x2
  IF arr(i) > max THEN max = arr(i)
  IF arr(i) < min THEN min = arr(i)
NEXT i
sv = (max + min) / 2
LOCATE 1, 50
PRINT sv
'disp
di x1, x2, 4
IF x1 >= x2 THEN GOTO 3

IF x1 + 1 = x2 THEN
  IF arr(x1) > arr(x2) THEN SWAP arr(x1), arr(x2)
  GOTO 3
END IF

xl1 = x1
xl2 = x2


1
di xl1, xl2, 1
IF arr(xl1) > sv THEN
2
  IF arr(xl2) < sv THEN
    SWAP arr(xl1), arr(xl2)
    xl1 = xl1 + 1
    xl2 = xl2 - 1
  ELSE
    xl2 = xl2 - 1
    di xl1, xl2, 1
    IF xl1 = xl2 THEN GOTO 4
    GOTO 2
  END IF
ELSE
  xl1 = xl1 + 1
END IF

IF xl1 < xl2 THEN GOTO 1
'IF arr(xl1) < sv THEN xl1 = xl1 + 1
'IF arr(xl1) < sv THEN xl1 = xl1 + 1
4
mark(xl1) = 14
disp
mark(xl1) = 0

IF xl1 = x2 THEN
  sort x1, xl1 - 1
ELSE
  IF arr(xl1) > sv THEN
    sort x1, xl1 - 1
    sort xl1, x2
  ELSE
    sort x1, xl1
    sort xl1 + 1, x2
  END IF
END IF
3
END SUB