I'm trying to implement a merge sort algorithm in MIPS using linked lists. I'm basically trying to translate this code: http://www.geeksforgeeks.org/merge-sort-for-linked-list/ However, I'm having some issues. The sorted list is incomplete as if it had lost an entire recursive branch, for example, this is the linked list to sort: 4 -> 3 -> 1 -> 2 And the output is: 1 -> 2 -> 4. And then comes an error when I try to write the list to a file (Runtime exception at 0x004003fc: address out of range 0x00000000). I'm guessing that's because I expect to print 4 numbers, but I only have 3 numbers in the list.
I think where I need help is in the MergeSort function, as I don't COMPLETELY understand what it actually does pointer-wise. This is what I think it does:
It receives as a parameter a pointer to a pointer to the head of the list. Inside the function, it creates the "head" pointer, and it points to the VALUE of headRef (in this case, &head was passed on main, so now "head" inside the function has the address of head in the main). Then it declares two pointers, a and b (in MIPS this would be like doing a = 0, and b = 0? I can't "declare" registers). Then it checks if the list has 1 or 0 elements and returns if it does. Otherwise, it splits the list into two halves with FrontBackSplit(head, &a, &b), but this is the tricky par... this function doesn't return anything. Instead, it modifies the pointers "a" and "b", to make them point to the first half of the list, and the second half, respectively. In MIPS, I would think this as two return values $v0 and $v1. Then it sorts the list recursively, starting from the left, but once again, it doesn't return anything... it modifies the pointer "a" and "b". Finally, it changes the value of the pointer to the head of the list to make it point to the new sorted list.
Because of so many **ptr and &ptr values, I'm confused on what to save on the stack. This is what I ahve so far, regarding that function:
# void mergesort(node** headRef)
# input $a0: head of the list
mergesort:
move $t0, $s3 # node* head = headRef
li $t1, 0 # node* a
li $t2, 0 # node* b
# if(head == NULL || head->next == NULL)
beqz $t0, mergesort_return
lw $t3, node_next($t0) # $t3 = head->next
beqz $t3, mergesort_return
move $a0, $t0
move $a1, $t1
move $a2, $t2
# save head and $ra
addi $sp, $sp, -8
sw $t0, 0($sp)
sw $ra, 4($sp)
jal frontbacksplit
# restore head and $ra
lw $t0, 0($sp)
lw $ra, 4($sp)
addi $sp, $sp, 8
# save output results
move $t1, $v0 # a now points to the first half + 1 (if odd) of the list (frontRef)
move $t2, $v1 # b now points to the second half of the list (backRef)
# save head, a, b and $ra
addi $sp, $sp, -16
sw $t0, 0($sp)
sw $t1, 4($sp)
sw $t2, 8($sp)
sw $ra, 12($sp)
# mergesort(a)
move $a0, $t1
jal mergesort
# restore registers and $ra
lw $t0, 0($sp)
lw $t1, 4($sp)
lw $t2, 8($sp)
lw $ra, 12($sp)
addi $sp, $sp, 16
# save head, a, b and $ra
addi $sp, $sp, -16
sw $t0, 0($sp)
sw $t1, 4($sp)
sw $t2, 8($sp)
sw $ra, 12($sp)
# mergesort(b)
move $a0, $t2
jal mergesort
# restore registers and $ra
lw $t0, 0($sp)
lw $t1, 4($sp)
lw $t2, 8($sp)
lw $ra, 12($sp)
addi $sp, $sp, 16
move $a0, $t1
move $a1, $t2
# save head, a, b and $ra
addi $sp, $sp, -16
sw $t0, 0($sp)
sw $t1, 4($sp)
sw $t2, 8($sp)
sw $ra, 12($sp)
jal sortedmerge
# restore registers and $ra
lw $t0, 0($sp)
lw $t1, 4($sp)
lw $t2, 8($sp)
lw $ra, 12($sp)
addi $sp, $sp, 16
move $s3, $v0 # s3 is the saved head of the original list declared in main
mergesort_return:
jr $ra
Well... I did it. This was a homework and hasn't been graded. I hope they don't think I copied it lol.
######### uses function frontbacksplit
######### WORKING
# mergesort
# input $a0: head of the list to merge
mergesort:
li $t0, 0 # head_one = NULL
li $t1, 0 # head_two = NULL
# base case
beqz $a0, mergesort_return
lw $t2, node_next($a0)
beqz $t2, mergesort_return
addi $sp, $sp, -8
sw $ra, 0($sp)
sw $a0, 4($sp)
# move $a0, $a0
move $a1, $t0
move $a2, $t1
jal frontbacksplit
move $t0, $v0
move $t1, $v1
lw $ra, 0($sp)
lw $a0, 4($sp)
addi $sp, $sp, 8
# mergesort(a)
addi $sp, $sp, -16
sw $ra, 0($sp)
sw $t0, 4($sp)
sw $t1, 8($sp)
sw $a0, 12($sp)
move $a0, $t0
jal mergesort # mergesort(a)
move $t9, $v0
lw $ra, 0($sp)
lw $t0, 4($sp)
lw $t1, 8($sp)
lw $a0, 12($sp)
addi $sp, $sp, 16
# mergesort(b)
addi $sp, $sp, -20
sw $ra, 0($sp)
sw $t0, 4($sp)
sw $t1, 8($sp)
sw $a0, 12($sp)
sw $t9, 16($sp)
move $a0, $t1
jal mergesort # mergesort(b)
move $t8, $v0
lw $ra, 0($sp)
lw $t0, 4($sp)
lw $t1, 8($sp)
lw $a0, 12($sp)
lw $t9, 16($sp)
addi $sp, $sp, 20
# t8 = a, t9 = b
addi $sp, $sp, -24
sw $ra, 0($sp)
sw $t0, 4($sp)
sw $t1, 8($sp)
sw $a0, 12($sp)
sw $t9, 16($sp)
sw $t8, 20($sp)
move $a0, $t8
move $a1, $t9
jal merge
lw $ra, 0($sp)
lw $t0, 4($sp)
lw $t1, 8($sp)
lw $a0, 12($sp)
lw $t9, 16($sp)
lw $t8, 20($sp)
addi $sp, $sp, 24
#move $v0, $v0
jr $ra
mergesort_return:
move $v0, $a0
jr $ra
######### WORKING
# input $a0: source node (list to split)
# input $a1: front ref (a) $s4
# input $a2: back ref (b) $s5
# output $v0: frontRef
# output $v1: backRef
frontbacksplit:
# $a0 = node* source, $a1 = node* frontRef, $a2 = node* backRef
move $t0, $a0 # $t0 = source
move $t1, $a1 # $t1 = frontRef
move $t2, $a2 # $t2 = backRef
li $t3, 0 # node* fast;
li $t4, 0 # node* slow;
# if(source == NULL)
beqz $t0, frontbacksplit_sorted
lw $t5, node_next($t0) # $t5 = source->next
# if(source->next == NULL)
beqz $t5, frontbacksplit_sorted
# else
move $t4, $t0 # slow = source
lw $t3, node_next($t0) # fast = source->next
frontbacksplit_while:
# while(fast != NULL)
beqz $t3, frontbacksplit_endwhile
lw $t3, node_next($t3) # fast = fast->next
# if(fast != NULL)
beqz $t3, frontbacksplit_while
lw $t4, node_next($t4) # slow = slow->next
lw $t3, node_next($t3) # fast = fast->next
j frontbacksplit_while
frontbacksplit_endwhile:
move $t1, $t0 # frontRef = source
lw $t2, node_next($t4) # backRef = slow->next
sw $zero, node_next($t4) # slow->next = NULL
move $v0, $t1
move $v1, $t2
j frontbacksplit_end
frontbacksplit_sorted:
move $v0, $t0 # frontRef = source
li $v1, 0 # backRef = NULL
frontbacksplit_end:
jr $ra
############ WORKING
# input $a0: head of the first list
# input $a1: head of the second list
# output $v0: pointer to the head of the merged-sorted list
merge:
beqz $a0, merge_return2
beqz $a1, merge_return1
li $t3, 0 # head_three = NULL
lw $t0, node_int($a0)
lw $t1, node_int($a1)
addi $sp, $sp, -16
sw $ra, 0($sp)
sw $a0, 4($sp)
sw $a1, 8($sp)
sw $t3, 12($sp)
bge $t0, $t1, merge_else
# if head_one->num < head_two->num
lw $a0, node_next($a0)
# $a1 already has head_two
jal merge
move $t0, $v0 # ptr = merge(head_one->next, head_two)
# restore values
lw $ra, 0($sp)
lw $a0, 4($sp)
lw $a1, 8($sp)
lw $t3, 12($sp)
move $t3, $a0
sw $t0, node_next($t3)
move $v0, $t3
addi $sp, $sp, 16
jr $ra
merge_else:
# $a0 already has head_one
lw $a1, node_next($a1)
jal merge
move $t0, $v0 # ptr = merge(head_one->next, head_two)
# restore values
lw $ra, 0($sp)
lw $a0, 4($sp)
lw $a1, 8($sp)
lw $t3, 12($sp)
move $t3, $a1
sw $t0, node_next($t3)
move $v0, $t3
addi $sp, $sp, 16
jr $ra
merge_return1:
move $v0, $a0
jr $ra
merge_return2:
move $v0, $a1
jr $ra
I know it's quite messy but it works :P.