I was intrigued by the recent sorting examples that have been posted. I was also wondering why quicksort was slower than some of the other sorts. So, I found a version of quicksort I have used in the past, converted it to BASIC, and inserted it into the test harness provided by codeguy and Zom-B. And it appears to be faster than the one included.

Wanting to see if I could get it a little more speed out of it, I converted all the implicit declarations similar to "i&" to explicit declarations of "dim i as long". But this actually made it somewhat slower. Any ideas why?

Here is the first, fast version, with variables using implicit declaration, and the trailing '&' character:

`sub quicksort4(array(), l&, r&)`

dim stack_l&(30)

dim stack_r&(30)

sp& = 0

lt& = l&

rt& = r&

do

do while lt& < rt&

n& = rt& - lt& + 1

if n& = 2 then

if array(lt&) > array(rt&) then swap array(lt&), array(rt&)

exit do

end if

if n& = 3 then

m& = lt& + 1

if array(lt&) > array(m&) then swap array(lt&), array(m&)

if array(lt&) > array(rt&) then swap array(lt&), array(rt&)

if array(m&) > array(rt&) then swap array(m&), array(rt&)

exit do

end if

middle = array((lt& + rt&) \ 2)

i& = lt&

j& = rt&

do

while array(i&) < middle: i& = i& + 1: wend

while array(j&) > middle: j& = j& - 1: wend

if i& <= j& then

if i& < j& then swap array(i&), array(j&)

i& = i& + 1

j& = j& - 1

end if

loop while i& <= j&

if j& - lt& < rt& - i& then

if i& < rt& then

sp& = sp& + 1

stack_l&(sp&) = i&

stack_r&(sp&) = rt&

end if

rt& = j&

else

if lt& < j& then

sp& = sp& + 1

stack_l&(sp&) = lt&

stack_r&(sp&) = j&

end if

lt& = i&

end if

loop

if sp& = 0 then exit do

lt& = stack_l&(sp&)

rt& = stack_r&(sp&)

sp& = sp& - 1

loop

end sub

And here is the second, slower version. The only (intentional) difference is that variables are explicitly declared as long via dim:

`sub quicksort4(array(), l as long, r as long)`

dim stack_l(30) as long

dim stack_r(30) as long

dim sp as long

dim lt as long

dim rt as long

dim n as long

dim j as long

dim i as long

dim m as long

sp = 0

lt = l

rt = r

do

do while lt < rt

n = rt - lt + 1

if n = 2 then

if array(lt) > array(rt) then swap array(lt), array(rt)

exit do

end if

if n = 3 then

m = lt + 1

if array(lt) > array(m) then swap array(lt), array(m)

if array(lt) > array(rt) then swap array(lt), array(rt)

if array(m) > array(rt) then swap array(m), array(rt)

exit do

end if

middle = array((lt + rt) \ 2)

i = lt

j = rt

do

while array(i) < middle: i = i + 1: wend

while array(j) > middle: j = j - 1: wend

if i <= j then

if i < j then swap array(i), array(j)

i = i + 1

j = j - 1

end if

loop while i <= j

if j - lt < rt - i then

if i < rt then

sp = sp + 1

stack_l(sp) = i

stack_r(sp) = rt

end if

rt = j

else

if lt < j then

sp = sp + 1

stack_l(sp) = lt

stack_r(sp) = j

end if

lt = i

end if

loop

if sp = 0 then exit do

lt = stack_l(sp)

rt = stack_r(sp)

sp = sp - 1

loop

end sub

Thanks for any help!