.data
list: .space 1000
Left: .space 1000
Right: .space 1000
n: .word 0
arraySize: .word 0
arrayEndAddress:.word 0
prompt1: .asciiz "Enter n: "
prompt2: .asciiz "Enter element "
dialog1: .asciiz "The size of array entered is not power of 2!"
dialog2: .asciiz "The sorted list is: "
space: .asciiz " "
colon: .asciiz ": "
eol: .asciiz "\n"
dummy: .asciiz "Blah Blah Blah"
.text
main:
la $a0, prompt1
li $v0, 4
syscall
li $v0, 5
syscall
sw $v0, n
#move $t0, $v0
#move $t1, $v0
lw $t1, n
sll $t1, $t1, 2
li $t2, 1
la $t0, list
writeElements:
beq $t1, $zero, done
la $a0,prompt2
li $v0, 4
syscall
move $a0, $t2
li $v0, 1
syscall
la $a0,colon
li $v0, 4
syscall
li $v0, 5
syscall
sw $v0, 0($t0)
add $t0, $t0, 4
sub $t1, $t1, 4
add $t2, $t2, 1
j writeElements
done:
sw $t0, arrayEndAddress
la $t1, list
sub $t0, $t0, $t1
sw $t0, arraySize
jal mergeSort
jal printArray
j exit
exit:
li $v0, 10
syscall
mergeSort:
add $sp, $sp, -4
sw $ra, 0($sp)
#la $a0, list
lw $t0, n #get the number of elements
li $t1, 1 #curr_size
sub $t0, $t0, 1
for1:
sleu $s5, $t1, $t0
beqz $s5 endFor1
# $t2=left_start
# $t4=mid
# $t5=right_end
#li $t2, 0
#li $t4, 0
#li $t5, 0
and $t2, $t2, 0
and $t4, $t4, 0
and $t5, $t5, 0
for2:
sltu $s6, $t2, $t0
beqz $s6, endfor2
addu $t4, $t2, $t1
subu $t4, $t4, 1
sll $t5, $t1,1
addu $t5,$t5, $t2
subu $t5, $t5, 1
findMin: blt $t5, $t0, min
move $t5, $t0
min:
move $t5, $t5
#list,$t2, $t4, $t5
jal merge
sll $s1, $t1, 1
addu $t2, $t2, $s1
j for2
endfor2:
sll $t1, $t1,1
j for1
endFor1:
b doneMergeSort
doneMergeSort:
lw $ra, 0($sp)
jr $ra
merge:
# params: list, l=$t2, m=$t4, r=$t5
add $sp, $sp, -12
sw $ra, 0($sp)
sw $s1, 4($sp)
sw $t2, 8($sp)
sw $t1, 12($sp)
#sw $t0, 16($sp)
#ori $t0, $zero, 0 #n1
#ori $t3, $0, 0 #n2
addiu $t9, $t4, 1
subu $t9, $t9, $t2
subu $t3, $t5, $t4
li $s1, 0 #i
li $t7, 0#j
sll $t7, $t7, 2
LeftInput:
bge $s1, $t9, doneLeft
add $s2, $t2, $s1
sll $s2,$s2,2
lw $s3, list($s2)
sw $s3, Left($t7)
add $s1, $s1, 1
add $t7, $t7, 4
j LeftInput
doneLeft:
li $s1, 0
li $t7, 0
#sll $t6, $t3, 2
j RightInput
RightInput:
bge $s1, $t3, combine
#bge $t7, $t6, combine
add $s2, $t4, 1
add $s2, $s2, $s1
sll $s2, $s2, 2
lw $s3, list($s2)
add $t7,$t7, $s1
sll $t7, $t7, 2
sw $s3, Right($t7)
add $s1, $s1, 1
j RightInput
combine:
#t0=n1, $t2=l, $t3=n2
li $t1, 0 #actual memory address
li $t7, 0 #i=0
li $t4, 0 #actual memory address
li $t8, 0 #j
sll $t5, $t2, 2 #$t2=$t5=k=l
while1:
bge $t7, $t9, while2
bge $t8, $t3, while2
sll $t1, $t7, 2
sll $t4, $t8, 2
lw $s1, Left($t1)
lw $s2, Right($t4)
if1:
bgt $s1, $s2, else1
#sll $t1,$t7, 2
lw $s3, Left($t1)
#sll $t5, $t7, 2
sw $s3, list($t5)
add $t7, $t7, 1
j whileLoop1
else1:
#sll $t4,$t8, 2
lw $s3, Right($t4)
#sll $t5, $t8, 2
sw $s3, list($t5)
add $t8, $t8, 1
j whileLoop1
whileLoop1:
add $t5, $t5, 4
j while1
while2:
bge $t7, $t9, while3
sll $t1,$t7, 2
lw $s3, Left($t1)
sw $s3, list($t5)
add $t7, $t7, 1
add $t5, $t5, 4
j while2
while3:
bge $t8, $t3, combineDone
sll $t4,$t8, 2
lw $s3, Right($t4)
sw $s3, list($t5)
add $t8, $t8, 1
add $t5, $t5, 4
j while3
combineDone:
j doneMerge
doneMerge:
#la $a0, dummy
# li $v0, 4
# syscall
# la $a0, eol
# li $v0, 4
# syscall
lw $ra, 0($sp)
lw $s1, 8($sp)
lw $t2, 4($sp)
lw $t1, 12($sp)
#lw $t0, 16($sp)
jr $ra
printArray:
#add $sp, $sp,-4
la $a0, dialog2
li $v0, 4
syscall
li $t0, 0
lw $t1, n
sll $t1, $t1, 2
loop:
bge $t0, $t1, donePrint
lw $a0, list($t0)
li $v0, 1
syscall
la $a0, space
li $v0, 4
syscall
add $t0, $t0, 4
j loop
la $a0, eol
li $v0, 4
syscall
donePrint:
#lw $ra, 0($sp)
jr $ra