Write a program to merge two sorted arrays to create a third sorted array contai
ID: 3548353 • Letter: W
Question
Write a program to merge two sorted arrays to create a third sorted array containing all values from the two original arrays. PLEASE INCLUDE COMMENTS !!!
Merge is a key component to the mergesort algorithm. Suppose we have two sorted array A and B. We want to create array C which contains all values from A and B, in sorted order. Merge looks at one element from each of A and B, and puts the smaller one into array C. When all elements of A or B have been copied into C, the remaining elements from the other array are copied into C.
The pseudocode for merge is:
Hint: Think carefully about the subscripts you need for the three arrays.
Explanation / Answer
.data
A: .space 28 #space for 7 ints
B: .space 20 #space for 5 ints
C: .space 48 #space for 12 ints
prompt1: .asciiz "Enter next integer to put into A :"
prompt2: .asciiz "Enter next integer to put into B :"
text: .asciiz "After merging, the list of integers is:"
space: .asciiz " "
.text
.globl main
main:
la $t2, A #load address of A to t2
#Taking inputs from user and inserting in A
li $t0, 7
p1:
beq $zero,$t0,next #if 7 inputs taken then exit loop
li $v0, 4
la $a0, prompt1
syscall #display prompt message
li $v0, 5
syscall
sw $v0, 0($t2) #store into array
addi $t2, $t2, 4 #point to next element in array
addi $t0,$t0,-1
j p1
#same as above for B
next:
la $t3, B #load address of B to t5
#Taking inputs from user and inserting in B
li $t0, 5
p2:
beq $zero,$t0,sort #if 5 inputs taken then exit loop
li $v0, 4
la $a0, prompt2
syscall #display prompt message
li $v0, 5
syscall
sw $v0, 0($t3) #store into array
addi $t3, $t3, 4 #point to next element in array
addi $t0,$t0,-1
j p2
#merging part
sort:
la $s0, C #load address of C to s0
la $t1, A
la $t5, B
li $t0, 12
li $s3, 5
li $s2,7
sortmain:
beqz $s3,anext
beqz $s2,bnext
beqz $t0,end
lw $s5,0($t1)
lw $s6,0($t5)
slt $v0,$s5,$s6
beqz $v0,s1
#if element in a is smaller than elem in b
sw $s5,0($s0)
addi $t1, $t1, 4
addi $s0, $s0, 4
addi $t0,$t0,-1
subi $s2,$s2,1
j sortmain
#if element in b is smaller than elem in a
s1:
sw $s6,0($s0)
addi $t5, $t5, 4
addi $s0, $s0, 4
addi $t0,$t0,-1
subi $s3, $s3, 1
j sortmain
bnext:
beqz $t0,end
lw $s6,0($t5)
sw $s6,0($s0)
addi $s0,$s0,4
addi $t5,$t5,4
addi $t0,$t0,-1
j bnext
anext:
beqz $t0,end
lw $s6,0($t1)
sw $s6,0($s0)
addi $s0,$s0,4
addi $t1,$t1,4
addi $t0,$t0,-1
j anext
#final printing
end:
li $v0, 4
la $a0, text
syscall
la $t3, C
li $t0, 12
#loop for printing 12 numbers
print:
beqz $t0,exit
lw $a0,0($t3)
li $v0,1
syscall
li $v0, 4
la $a0, space
syscall
addiu $t3, $t3, 4
addi $t0,$t0,-1
j print
exit:
li $v0, 10
syscall
#The comments are not complete but they should give you a rough idea. As said am in a hurry rite now.
#Have rectified the errors. See if they work.. beq was a typo it should be beqz
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.