home *** CD-ROM | disk | FTP | other *** search
/ C!T ROM 5 / ctrom5b.zip / ctrom5b / PROGRAM / ASM / ALIB30B / SORT23.ASM < prev    next >
Assembly Source File  |  1994-11-12  |  5KB  |  207 lines
  1. ;***************************** SORT23.ASM ***********************************
  2.  
  3. LIBSEG           segment byte public "LIB"
  4.         assume cs:LIBSEG , ds:nothing
  5. ;----------------------------------------------------------------------------
  6. .xlist
  7.     include  mac.inc
  8.     extrn    dos_mem_allocate:far
  9.     extrn    dos_mem_release:far
  10. .list
  11. comment 
  12. ;- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -(  SORT   )
  13. ; merge_sort_arrayw - sort array of words. 
  14. ;  inputs:  ds:0 - ptr to word array
  15. ;              cx - number of elements in array (range 2-16383)
  16. ;
  17. ;  Output:  if no carry array is sorted in decending order
  18. ;           carry = insufficient memory
  19. ;           
  20. ;  Note:  merge_sort_arrayw uses 290 bytes for code and allocates
  21. ;         memory to hold array being sorted.
  22. ; 
  23. ;  Psuedo code:
  24. ;
  25. ;int array2sort[n]; /* array with indexes from 0 to n-1 as in C */
  26. ;                   /* replace int with whatever datatype you want to sort */
  27. ;int l;          /* length of sorted sets */
  28. ;int first;      /* first element to be sorted */
  29. ;  l=1;
  30. ;  while (l<n)
  31. ;  {
  32. ;    first=0;
  33. ;    while (first+l<n)
  34. ;    {
  35. ;      merge(array2sort[first..first+l-1], array2sort[first+l..first+2*l-1]);
  36. ;      first= first + 2 * l;
  37. ;    }
  38. ;    l= 2*l; /* We now have sorted sets of length 2*l */
  39. ;  }
  40. ;****************************
  41. 
  42. work_seg        dw    0    ;temp index sort area
  43. sort_buffer_seg        dw    0
  44. delta            dw    0
  45. no_sort_flag        db    0    ;set =1 if no sort in merge pass
  46. sorted_flag        db    0    ;set =1 if index already sorted
  47.  
  48.     public    merge_sort_arrayw              
  49. merge_sort_arrayw    proc    far
  50.     apush    ax,bx,cx,dx,si,di,bp,ds,es
  51.     cld
  52.     cmp    cx,1
  53.     jbe    sort_exit        ;jmp if not enough data to sort
  54.     shl    cx,1
  55.     mov    bp,cx            ;bp=sort buffer length (bytes)
  56.     mov    cs:sort_buffer_seg,ds
  57. ;
  58. ; allocate work area
  59. ;
  60.     mov    dx,0
  61.     mov    ax,bp
  62.     call    dos_mem_allocate
  63.     jc    sort_exit3
  64.     mov    cs:work_seg,es
  65.     mov    cs:delta,2
  66.  
  67.         mov    di,cs:delta        ;setup list2 start
  68. lp1:    mov    bx,0            ;setup store ptr for 'merge' routine
  69.     mov    si,0                     ;set si at top of buffer
  70.     mov    cs:sorted_flag,1    ;preload already sorted flag
  71.     
  72. lp2:    call    merge
  73.     mov    cl,cs:no_sort_flag    ;get 1 if no sort occured
  74.     and    cs:sorted_flag,cl    ;keep 1 in sorted_flag if block sorted
  75.     add    si,cs:delta
  76.     add    di,cs:delta
  77.     cmp    si,bp            ;bp=sort buffer length
  78.     jb    lp2            ;jmp if more data to sort
  79. ;
  80. ; move the temp index back to origional
  81. ;    
  82. ms_4:    cmp    cs:sorted_flag,1
  83.     je    ms_done            ;jmp if no sort needed
  84.  
  85.     mov    di,cs:delta
  86.     shl    di,1
  87.     mov    cs:delta,di
  88.     cmp    di,bp            ;check if delta > buffer length
  89.     jae    ms_done
  90. ;
  91.     mov    ax,ds            ;swap
  92.     mov    cx,es            ;  buffer
  93.     mov    ds,cx            ;    pointers
  94.     mov    es,ax            ;       ds & es
  95.     jmp    lp1
  96.  
  97. ms_done:
  98.     mov    ax,ds
  99.     cmp    ax,cs:sort_buffer_seg    ;check if good data in work seg
  100.     jne    sort_exit2        ;jmp if sort data in sort_buffer
  101.         
  102.     mov    cx,bp            ;bp=sort_buffer_length
  103.     shr    cx,1            ;length
  104.     mov    di,0            ;destination
  105.     mov    si,0            ;source
  106.     mov    es,cs:sort_buffer_seg
  107.     mov    ds,cs:work_seg
  108.     rep    movsw            ;move work index -> origional index
  109. sort_exit2:    
  110.     mov    es,cs:work_seg
  111.     call    dos_mem_release    
  112. sort_exit:
  113.     clc
  114. sort_exit3:
  115.     apop    es,ds,bp,di,si,dx,cx,bx,ax
  116.     retf
  117. merge_sort_arrayw    endp
  118.  
  119. ;--------------------------------------------------------------------
  120. ; MERGE - combine two sorted lists
  121. ;   inputs:  ds:si = list1 index top
  122. ;            ds:di = list2 index top, (may be short list)
  123. ;          cs:delta = length of each list
  124. ;            es:bx = active storage pointer of work area
  125. ;               bp = sort buffer length (byte count)
  126. ;
  127. ;  output: si,di updated to end of field
  128. ;
  129. starting_list2_len    dw    0
  130.  
  131. merge:    mov    cs:no_sort_flag,0    ;preload data unsorted state
  132.     mov    cx,cs:delta        ;get list1 length
  133.     mov    dx,cx            ;set list2 length
  134. ;
  135. ; check length of list2
  136. ;    
  137.     mov    ax,dx            ;get list2 length
  138.     add    ax,di            ;compute last location
  139.     sub    ax,bp            ;ax = list2 length adjustment
  140.     jb    mer_cont2        ;jmp if length ok
  141.     sub    ax,cx
  142.     jbe    mer_cont1        ;jmp if only list2 needs adjusting
  143.     mov    dx,0            ;list2 is zero length
  144. ;
  145. ; adjust list1 length
  146. ;
  147.     sub    cx,ax
  148.     jmp    mer_cont2
  149. ;
  150. ; adjust list2 length
  151. ;
  152. mer_cont1:    
  153.     add    ax,cx
  154.     sub    dx,ax            ;adjust list2 length
  155. mer_cont2:
  156.     mov    cs:starting_list2_len,dx
  157. ;
  158. ;             bp=sort buffer length    ds:si=list1 ptr  cx=list1 length  
  159. ; ax=scratch  es:bx=store ptr          ds:di=list2 ptr  dx=list2 length
  160. ;
  161. m_lp:    cmp    cx,0
  162.     je    sort2_only        ;jmp if list1 length=0
  163.     cmp    dx,0
  164.     je    move1            ;jmp if list2 length=0
  165. ;
  166. ; both lists have valid records, do compare
  167. ;
  168.     mov    ax,word ptr ds:[si]
  169.     cmp    ax,word ptr ds:[di]
  170.     ja    move2            ;jmp if list2 data smaller
  171.     jmp    move1            ;jmp if list1 data smaller    
  172. ;
  173. ; list1 is empty, check list2
  174. ;
  175. sort2_only:
  176.     cmp    dx,0            ;check if list2 has data
  177.     je    merge_done1        ;jmp if end of both lists
  178. ;
  179. ; check if no sort was needed for list1, (everything already sorted)
  180. ;
  181.     cmp    dx,cs:starting_list2_len ;has list2 data been merged
  182.     jne    sort2_cont        ;jmp if merge occured
  183.     mov    cs:no_sort_flag,1    ;set no sort this pass flag
  184. sort2_cont:    
  185. ;
  186. ; list2 has data move it
  187. ;
  188. move2:    mov    ax,word ptr ds:[di]    ;get list2 data
  189.     add    di,2
  190.     sub    dx,2            ;list2 length - 2
  191.     jmp    do_move
  192. ;
  193. ; list1 has data move it
  194. ;
  195. move1:    lodsw
  196.     sub    cx,2            ;list1 length - 2
  197. do_move:mov    word ptr es:[bx],ax
  198.     add    bx,2
  199.     jmp    m_lp
  200. ;
  201. merge_done1:
  202.     ret
  203.  
  204. ;
  205. LIBSEG    ENDS
  206.     end
  207.