Write a \"merge\" program that merges two ordered lists of integers into a new o

Question

Write a "merge" program that merges two ordered lists of integers into a new ordered list. For example, given two ordered lists (1.4.6.9) and (0, 2, 3, 7) as input arguments, "merge" should produce a new list (0.1.2, 3.4.6.7.9) which is also ordered. Another example could be to merge (-3.0.6) and (-2.0.4.5.9) to produce (-2.-3.0.0.4, 5.6.9). The "merge" program assumes that the two input lists (in increasing order) of integers are stored in the data area. It loads the integers and merges them into an ordered list. The resulting ordered list (e.g. (-2, -3, 0, 0, 4, 5, 6, 9)) should be stored back into the data area. It is at your own choice how the data area (i.e. the lists) is arranged, and whether the resulting list is overwritten onto the original two lists. But be sure to give meaningful labels and clearly indicate (using label or comments) where the merged list is stored. Before your program terminates, it should print out the merged list which should be in increasing order.

Explanation / Answer

the program for MIPS merge sort is as follows

.text

   la   $a0, info      
   lw   $t0, length      
   sll   $t0, $t0, 2      
   add   $a1, $a0, $t0      
   jal   mergesort      
   b   sortend          
  
# mergesort

mergesort:

   addi   $sp, $sp, -16      
   sw   $ra, 0($sp)      
   sw   $a0, 4($sp)      
   sw   $a1, 8($sp)      
  
   sub    $t0, $a1, $a0      

   ble   $t0, 4, mergesortend  
  
   srl   $t0, $t0, 3      
   sll   $t0, $t0, 2      
   add   $a1, $a0, $t0      
   sw   $a1, 12($sp)      
   jal   mergesort      
  
   lw   $a0, 12($sp)      
   lw   $a1, 8($sp)      
  
   jal   mergesort      
  
   lw   $a0, 4($sp)      
   lw   $a1, 12($sp)      
   lw   $a2, 8($sp)      
  
   jal   merge          
  
mergesortend:              

   lw   $ra, 0($sp)      
   addi   $sp, $sp, 16      
   jr   $ra           # Return
  

merge:
   addi   $sp, $sp, -16      
   sw   $ra, 0($sp)         
   sw   $a0, 4($sp)         
   sw   $a1, 8($sp)         
   sw   $a2, 12($sp)         
  
   move   $s0, $a0         
   move   $s1, $a1         
  
mergeloop:

   lw   $t0, 0($s0)         
   lw   $t1, 0($s1)         
   lw   $t0, 0($t0)         
   lw   $t1, 0($t1)         
  
   bgt   $t1, $t0, noshift     
  
   move   $a0, $s1         
   move   $a1, $s0         
   jal   shift             
   addi   $s1, $s1, 4         
noshift:
   addi   $s0, $s0, 4   #the 4 for basic addi     
   lw   $a2, 12($sp)         
   bge   $s0, $a2, mergeloop     
   bge   $s1, $a2, mergeloop     
   b   mergeloop
  
mergeloop:
  
   lw   $ra, 0($sp)         
   addi   $sp, $sp, 16         
   jr    $ra             

shift:
   li   $t0, 10
   ble   $a0, $a1, shiftend     
   addi   $t6, $a0, -4         
   lw   $t7, 0($a0)         
   lw   $t8, 0($t6)         
   sw   $t7, 0($t6)         
   sw   $t8, 0($a0)         
   move   $a0, $t6         
   b    shift             
shiftend:
   jr   $ra             
  
sortend:                 

# Print out the array
   li   $t0, 0                 
prloop:
   lw   $t1,length             
   bge   $t0,$t1,prdone             
   sll   $t2,$t0,2             
   lw   $t3,info($t2)             
   lw   $a0,0($t3)             
   li   $v0,1              
   syscall                     
   la   $a0,eol                 
   li   $v0,4              
   syscall                   #
   addi   $t0,$t0,1             
   b   prloop                 
prdone:                         
   li   $v0,10
   syscall
   .data
eol:   .asciiz   " "

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.