Can anyone help me with this merge sort. For some reason the test cases that are

Question

Can anyone help me with this merge sort. For some reason the test cases that are being run on it are not working...

merge_sort:

# save return pointer to stack

addiu $sp, $sp, -4 # allocate space for 1 value

sw $ra, 0($sp)

# save regs to stack

addiu $sp, $sp, -32 # allocate space for 8 values

sw $s0, 0($sp)

sw $s1, 4($sp)

sw $s2, 8($sp)

sw $s3, 12($sp)

sw $s4, 16($sp)

sw $s5, 20($sp)

sw $s6, 24($sp)

sw $s7, 28($sp)

# save parameters

move $s0, $a1 # size of array (in entries)

sll $s1, $s0, 2 # size of array (int bytes)

move $s2, $a0 # pointer to array

# if size < 2 then return

sltiu $t0, $s0, 2 # t0 = a0 < 2

bgtz $t0, mergereturn # if t0 return

# s3 = allocate temporary array

subu $sp, $sp, $s1

move $s3, $sp

# s4 = number of entries in first half

srl $s4, $s0, 1

# call merge_sort on first half

addiu $sp, $sp, -8 # allocate space for 2 parameters

move $a1, $s4 # a0 = size of array (in 4-byte entries)

move $a0, $s3 # a1 = pointer to head of array

jal merge_sort # call the function

addiu $sp, $sp, 8 # deallocate space on the stack

# number of entries in second half, s5 = s0 - s4

subu $s5, $s0, $s4

# t0 = size of first half (in bytes)

sll $t0, $s4, 2 # t0 = s4 << 2

# s6 pointer to second half

addu $s6, $s3, $t0

# call merge_sort on second half

addiu $sp, $sp, -8 # allocate space for 2 parameters

move $a1, $s5 # a0 = size of array (in 4-byte entries)

move $a0, $s6 # a1 = pointer to head of array

jal merge_sort # call the function

addiu $sp, $sp, 8 # deallocate space on the stack

#####Merge######

# t0 = size of first half (in bytes)

sll $t0, $s4, 2 # t0 = s4 << 2

# t1 dest pointer

move $t1, $s2

# t2 src1 pointer

move $t2, $s3

# t3 src2 pointer

move $t3, $s6

# t4 end of second half

addu $t4, $s3, $s1

mergeloop:

# first or second are equal to their ends

beq $t2, $s6, finishfirst

beq $t3, $t4, finishfirst

# load entries

lw $t5, 0($t2)

lw $t6, 0($t3)

# second entry is less than first, so skip to mergesecond

slt $t7, $t6, $t5

bgtz $t7, mergesecond

# first entry is the smaller one

sw $t5, 0($t1) # save word

addiu $t1, $t1, 4 # increment dest

addiu $t2, $t2, 4 # increment first

j mergeloop

mergesecond:

# second entry is the smaller one

sw $t6, 0($t1) # save word

addiu $t1, $t1, 4 # increment dest

addiu $t3, $t3, 4 # increment second

j mergeloop

finishfirst:

beq $t2, $s6, finishsecond

lw $t5, 0($t2)

sw $t5, 0($t1) # save word

addiu $t1, $t1, 4 # increment dest

addiu $t2, $t2, 4 # increment first

j finishfirst

finishsecond:

beq $t3, $t4, copy

lw $t6, 0($t3)

sw $t6, 0($t1) # save word

addiu $t1, $t1, 4 # increment dest

addiu $t3, $t3, 4 # increment second

j finishsecond

# copy temp array to src

copy:

lw $t5, 0($s3) # load from temp array

sw $t5, 0($s2) # save word to array

addiu $s2, $s2, 4 # increment

addiu $s3, $s3, 4 # increment

bne $s3, $t4, copy

# free temporary array

addu $sp, $sp, $s1

mergereturn:

# restore saved regs from stack

lw $s0, 0($sp)

lw $s1, 4($sp)

lw $s2, 8($sp)

lw $s3, 12($sp)

lw $s4, 16($sp)

lw $s5, 20($sp)

lw $s6, 24($sp)

lw $s7, 28($sp)

addiu $sp, $sp, 32 # deallocate space for 8 values

# restore return pointer from stack

lw $ra, 0($sp)

addiu $sp, $sp, 4 # deallocate space for 1 value

# return

jr $ra # return to caller

# ==== Register $a0 contains array pointer ==== #

# ==== Register $a1 contains array length ===== #

Explanation / Answer

.data array: .word 8, 2, 7, 1, 5, 6, 3, 4, 9, 0 n: .word 10 .text .globl main main: lw $t0, n # $t0 contains n la $a0, array # $a0 contains address of array li $a1, 0 # $a1 contains starting index to sort (low) addi $a2,$t0,-1 # $a2 contains ending index to sort (high) jal mergeSort li $v0, 10 # system code for exit syscall endMain: .text .globl mergeSort # $a0 contains address of array to sort # $a1 contains low (starting index of array to sort) # $a2 contains high (ending index of array to sort) # $s0 contains address of array to sort # $s1 contains low (starting index of array to sort) # $s2 contains high (ending index of array to sort) # $s3 contains mid mergeSort: addi $sp, $sp, -20 # make room on stack for 5 registers sw $s0, 4($sp) # save $s0 on stack sw $s1, 8($sp) # save $s1 on stack sw $s2, 12($sp) # save $s2 on stack sw $s3, 16($sp) # save $s3 on stack sw $ra, 20($sp) # save $ra on stack move $s0, $a0 # copy param. $a0 into $s0 (addr array) move $s1, $a1 # copy param. $a1 into $s1 (low) move $s2, $a2 # copy param. $a2 into $s2 (high) if: blt $s1, $s2, then # if low

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---