-
Notifications
You must be signed in to change notification settings - Fork 1
/
InplaceMergeSort.asm
149 lines (115 loc) · 4.58 KB
/
InplaceMergeSort.asm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
.text
main:
la $a0, info # Load the start address of the array
lw $t0, length # Load the array length
sll $t0, $t0, 2 # Multiple the array length by 4 (the size of the elements)
add $a1, $a0, $t0 # Calculate the array end address
jal mergesort # Call the merge sort function
b sortend # We are finished sorting
mergesort:
addi $sp, $sp, -16 # Adjust stack pointer
sw $ra, 0($sp) # Store the return address on the stack
sw $a0, 4($sp) # Store the array start address on the stack
sw $a1, 8($sp) # Store the array end address on the stack
sub $t0, $a1, $a0 # Calculate the difference between the start and end address (i.e. number of elements * 4)
ble $t0, 4, mergesortend # If the array only contains a single element, just return
srl $t0, $t0, 3 # Divide the array size by 8 to half the number of elements (shift right 3 bits)
sll $t0, $t0, 2 # Multiple that number by 4 to get half of the array size (shift left 2 bits)
add $a1, $a0, $t0 # Calculate the midpoint address of the array
sw $a1, 12($sp) # Store the array midpoint address on the stack
jal mergesort # Call recursively on the first half of the array
lw $a0, 12($sp) # Load the midpoint address of the array from the stack
lw $a1, 8($sp) # Load the end address of the array from the stack
jal mergesort # Call recursively on the second half of the array
lw $a0, 4($sp) # Load the array start address from the stack
lw $a1, 12($sp) # Load the array midpoint address from the stack
lw $a2, 8($sp) # Load the array end address from the stack
jal merge # Merge the two array halves
mergesortend:
lw $ra, 0($sp) # Load the return address from the stack
addi $sp, $sp, 16 # Adjust the stack pointer
jr $ra # Return
merge:
addi $sp, $sp, -16 # Adjust the stack pointer
sw $ra, 0($sp) # Store the return address on the stack
sw $a0, 4($sp) # Store the start address on the stack
sw $a1, 8($sp) # Store the midpoint address on the stack
sw $a2, 12($sp) # Store the end address on the stack
move $s0, $a0 # Create a working copy of the first half address
move $s1, $a1 # Create a working copy of the second half address
mergeloop:
lw $t0, 0($s0) # Load the first half position pointer
lw $t1, 0($s1) # Load the second half position pointer
lw $t0, 0($t0) # Load the first half position value
lw $t1, 0($t1) # Load the second half position value
bgt $t1, $t0, noshift # If the lower value is already first, don't shift
move $a0, $s1 # Load the argument for the element to move
move $a1, $s0 # Load the argument for the address to move it to
jal shift # Shift the element to the new position
addi $s1, $s1, 4 # Increment the second half index
noshift:
addi $s0, $s0, 4 # Increment the first half index
lw $a2, 12($sp) # Reload the end address
bge $s0, $a2, mergeloopend # End the loop when both halves are empty
bge $s1, $a2, mergeloopend # End the loop when both halves are empty
b mergeloop
mergeloopend:
lw $ra, 0($sp) # Load the return address
addi $sp, $sp, 16 # Adjust the stack pointer
jr $ra # Return
shift:
li $t0, 10
ble $a0, $a1, shiftend # If we are at the location, stop shifting
addi $t6, $a0, -4 # Find the previous address in the array
lw $t7, 0($a0) # Get the current pointer
lw $t8, 0($t6) # Get the previous pointer
sw $t7, 0($t6) # Save the current pointer to the previous address
sw $t8, 0($a0) # Save the previous pointer to the current address
move $a0, $t6 # Shift the current position back
b shift # Loop again
shiftend:
jr $ra # Return
sortend: # Point to jump to when sorting is complete
# Print out the indirect array
li $t0, 0 # Initialize the current index
prloop:
lw $t1,length # Load the array length
bge $t0,$t1,prdone # If we hit the end of the array, we are done
sll $t2,$t0,2 # Multiply the index by 4 (2^2)
lw $t3,info($t2) # Get the pointer
lw $a0,0($t3) # Get the value pointed to and store it for printing
li $v0,1
syscall # Print the value
la $a0,eol # Set the value to print to the newline
li $v0,4
syscall # Print the value
addi $t0,$t0,1 # Increment the current index
b prloop # Run through the print block again
prdone: # We are finished
li $v0,10
syscall
.data
eol: .asciiz "\n"
# Some test data
eight: .word 83
five: .word 54
four: .word 42
nine: .word 94
one: .word 134
seven: .word 72
six: .word 634
ten: .word 104
three: .word 32
two: .word 224
# An array of pointers (indirect array)
length: .word 10 # Array length
info: .word seven
.word three
.word ten
.word one
.word five
.word two
.word nine
.word eight
.word four
.word six