 'bottom-up Merge-sort procedure
===============================
macro mergeSort(
  index,count,compare, 'params
  src,dest,stp,sw,kk,bi,bj,ej,ed,ni,nj,sx,dj,sd 'encapsulated
  )
'
' index      index array name
' count      element count
' compare    comparator callback/macro
'
#ifndef index
  int *index 'create the index file
  if @index then freememory @index                        'clear counter
  @index=getMemory 2*(count)*sx
  scope
  indexbase 1
  int i
  for i=1 to count
    index[i]=i 'initial value
  next
  end scope
#endif
'
sys src  = 0      ' index offset for elements to be compared
sys dest = 0      ' index offset for merged ordered elements
sys stp  = 0      ' merge group size X sizeof idx element
sys sw   = 0      ' flag to select from second group instead of first
sys kk   = 0      ' element counter
sys bi   = 0      ' base for first group
sys bj   = 0      ' base for second group
sys ej   = 0      ' boundary for second group
sys ed   = 0      ' source data boundary
int * ni          ' position for first compare element
int * nj          ' position for second compare element
int * dj          ' destination for element
%=  sx=sizeof int 'element size
sys sd=count*sx   'size of index data (bytes)
'
src=@index
dest=sd+@index
stp=sx 'INITIAL STRIDE IS SIZE OF IDX ELEMENT
do 'MERGING LOOP
  if stp>=sd then
    if src<>@index then 'COPY INDEX VALUES BACK TO BASE
      copy @index, @index+sd, sd
    endif
    exit do 'DONE
  end if
  kk=0
  bi=src : bj=bi+stp : ej=bj+stp
  @ni=bi : @nj=bj
  ed=src+sd 'DATA BOUNDARY
  LimitMax ej,ed
  @dj=dest-sx
  stp+=stp 'DOUBLE STRIDE FOR EACH MERGE 8,16,32 ...
  do 'NEXT MERGING PASS
    if kk>=count then exit do 'ALL ELEMENTS PROCESSED
    stride dj : kk++ 'NEXT DESTINATION POSITION
    retest:
    if @ni>=bj then
      if @nj>=ej then 'MOVE TO NEXT GROUP
        bi+=stp : bj+=stp : ej+=stp
        @ni=bi : @nj=bj
        LimitMax ej,ed 'LIMIT EJ TO BOUNDARY ed
        goto retest
      else
        dj=nj : stride nj : continue do 'PICK FROM SECOND GROUP
      end if
    elseif @nj>=ej then
      dj=ni : stride ni : continue do 'PICK FROM FIRST GROUP
    end if
    'COMPARE BEFORE PICKING
    sw=0
    compare sw, ni, nj 'COMPARE PROCEDURE
    if sw then dj=nj : stride nj else dj=ni : stride ni
  end do
  swap src,dest 'SWAP SOURCE/DESTINATION IDX BASES
end do
end macro

