define limit = 10, iterations = 6
define iteration, size, middle, plusone
define point, top, high, low, pivot

dim list[limit]
dim stack[limit]

for iteration = 1 to iterations

	gosub fill
	gosub median

next iteration

end

sub fill

	print "list: ",

	erasearray list

	let size = int(rnd * limit) + 1

	if size <= 2 then

		let size = 3

	endif

	for i = 0 to size - 1

		let list[i] = rnd * 1000 + rnd
		print list[i],

		gosub printcomma

	next i

return

sub median

	gosub sort

	print newline, "size: ", size, tab,

	let middle = int((size - 1)/ 2)
	print "middle: ", middle + 1, tab,

	if size mod 2 then

		print "median: ", list[middle]

	else

		let plusone = middle + 1
		print "median: ", (list[middle] + list[plusone]) / 2

	endif

	print

return

sub sort

	let low = 0
	let high = size - 1
	let top = -1

	let top = top + 1
	let stack[top] = low
	let top = top + 1
	let stack[top] = high

	do

		if top < 0 then

			break

		endif

		let high = stack[top]
		let top = top - 1
		let low = stack[top]
		let top = top - 1

		let i = low - 1
		
		for j = low to high - 1

			if list[j] <= list[high] then

				let i = i + 1
				let t = list[i]
				let list[i] = list[j]
				let list[j] = t

			endif

		next j

		let point = i + 1
		let t = list[point]
		let list[point] = list[high]
		let list[high] = t
		let pivot = i + 1

		if pivot - 1 > low then

			let top = top + 1
			let stack[top] = low
			let top = top + 1
			let stack[top] = pivot - 1

		endif

		if pivot + 1 < high then

			let top = top + 1
			let stack[top] = pivot + 1
			let top = top + 1
			let stack[top] = high

		endif

		wait

	loop top >= 0

	print newline, "sorted: ",

	for i = 0 to size - 1

		print list[i],
		gosub printcomma

	next i

return

sub printcomma

	if i < size - 1 then

		print comma, " ",

	endif

return