'By Fryer - Please Upload.
'Fast linear z-sort for large numbers of values.
'
'currently set up for 20 bit positive integers.
'sorts list by 4 bits on each pass with 6 passes but 
'can be customised to suit ranges and memory.
'MUST HAVE even No. of passes and last pass MUST
'be above range for values (in this case bits 21 to 24
'are always 0)

'set No. of values and allocate memory
'if mx is less than 11 display sorted list
  mx=10000
  dim c(15),oc(15),sort(mx*32),z(mx)

'create random list and put unsorted order into sort array
  for i=1 to mx
    z(i)=int(ran(1048575))
    sort(i)=i
  next i

'initialise sort variables (only required once)
  store=mx*16+1
  retrieve=1
  final=1/16/16/16/16/16/16

'start timer
  t1$=time$

'sort
  bit=1
  c(0)=mx+1
  repeat
    for i=0 to 15 oc(i)=c(i)
      c(i)=store+mx*i next i
    for i=0 to 15 p=retrieve+mx*i
      oc=oc(i)
      while(p<oc) sort=sort(p)
        b=and(15,z(sort)*bit)
        c=c(b)
        sort(c)=sort
        c(b)=c+1
        p=p+1 wend next i
    bit=bit/16
    t=retrieve
    retrieve=store
    store=t until(bit=final)

'stop timer
  t2$=time$

'check and display results
ocs=0:scs=0
fail=0
for i=1 to mx
if mx<11 print "  "+str$(z(sort(i)))+"  "+str$(z(i))
z=z(sort(i))
ocs=ocs+z(i)
scs=scs+z(sort(i))
if i>1 then
if z<oz fail=fail+1
fi
oz=z
next i
cs=ocs-scs
print" sorted "+str$(mx)+" values"
print" failure="+str$(fail)+"   Checksum="+str$(cs)
print" from "+t1$
print"   to "+t2$
















