-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMergeSort.asm
More file actions
197 lines (177 loc) · 5.51 KB
/
MergeSort.asm
File metadata and controls
197 lines (177 loc) · 5.51 KB
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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
.data #data directive : for variable
arr : .word 3,2,1,4,15,57,23,2,5,10,14,17,0,8,3 #arr to be sorted
temp : .space 36
temp1 : .space 36
gap : .asciiz " "
.
.text #text directive : for instruction
addi $sp,$sp,-8 #creating activation record for function call i.e sort
move $t8,$zero
addi $t9,$zero,14
sw $t8,($sp)
sw $t9,4($sp)
jal sort # call to sort
la $t0,arr # get base address of arr to be sorted
add $s0,$zero,$zero
j print # jump to print function
sort : # Sort function
addi $sp,$sp,-4
sw $ra,($sp)
lw $t8,4($sp) # t8 <- start index
lw $t9,8($sp) # t9 <- end index
bge $t8,$t9,more # check if start>=end
add $t7,$t8,$t9
div $t7,$t7,2 # t7 <- (start+end)/2
#First sort called
addi $sp,$sp,-8
sw $t8,0($sp)
sw $t7,4($sp)
jal sort
addi $sp,$sp,8 # removing it's record
# second sort called
lw $t8,4($sp)
lw $t9,8($sp)
add $t7,$t8,$t9
div $t7,$t7,2
addi $t7,$t7,1
addi $sp,$sp,-8
sw $t7,0($sp) # storing value in stack
sw $t9,4($sp)
jal sort
addi $sp,$sp,8
#merge called
lw $t8,4($sp)
lw $t9,8($sp)
add $t7,$t8,$t9
div $t7,$t7,2
move $a0,$t8 #a0,a1,a2 argument for merge
move $a1,$t7 # a0 <- start,a1 <- mid,a2 <-end
move $a2,$t9
jal merge #call to merge function
lw $ra,($sp)
addi $sp,$sp,4
jr $ra
more: # this is called when sort return when start>=end
lw $ra,0($sp)
addi $sp,$sp,4
jr $ra
merge : # merge procedure
move $t6,$a1
addi $t6,$t6,1
move $s7,$a0
move $t5,$a0
sub $a0,$a1,$a0
sub $a1,$a2,$a1
sub $a1,$a1,1
move $s0,$zero
move $s1,$zero
loop: # loop fill start to mid in temp
bgt $s0,$a0,loop1
mul $s0,$s0,4 #arr[4] = arr +4*4 as each element is of 4 byte
mul $t5,$t5,4
la $t0,temp
la $t2,arr
add $t0,$t0,$s0
add $t2,$t2,$t5
lw $s6,($t2)
sw $s6,($t0)
div $s0,$s0,4
div $t5,$t5,4
addi $s0,$s0,1
addi $t5,$t5,1
j loop
loop1: # loop1 fill mid+1 to end in temp1
bgt $s1,$a1,loop2
mul $s1,$s1,4 #arr[4] = arr +4*4 as each element is of 4 byte
mul $t6,$t6,4
la $t0,temp1
la $t2,arr
add $t0,$t0,$s1
add $t2,$t2,$t6
div $s1,$s1,4
div $t6,$t6,4
lw $s6,($t2)
sw $s6,($t0)
addi $s1,$s1,1
addi $t6,$t6,1
j loop1
loop2: # loop2 prepare variables for loop3
move $s0,$zero
move $s1,$zero
add $s7,$s7,$zero
j loop3
loop3: #loop3 merge two sorted array temp,temp1 and place in arr
bgt $s0,$a0,loop4
bgt $s1,$a1,loop4
la $t0,arr
la $t1,temp
la $t2,temp1
mul $s0,$s0,4
mul $s1,$s1,4
mul $s7,$s7,4
add $t1,$t1,$s0
add $t2,$t2,$s1
add $t0,$t0,$s7
div $s7,$s7,4
div $s1,$s1,4
div $s0,$s0,4
lw $t4,($t1)
lw $t5,($t2)
ble $t4,$t5,if # check if temp[idx] <= temp1[idx1]
sw $t5,($t0)
addi $s1,$s1,1
addi $s7,$s7,1
j loop3
if :
sw $t4,($t0)
addi $s0,$s0,1
addi $s7,$s7,1
j loop3
loop4: # loop4 is to fill remaining element of temp1 in array
bgt $s1,$a1,loop5
la $t0,temp1
la $t2,arr
add $s7,$s7,$zero
mul $s1,$s1,4
mul $s7,$s7,4
add $t0,$t0,$s1
add $t2,$t2,$s7
div $s7,$s7,4
div $s1,$s1,4
lw $t4,($t0)
sw $t4,($t2)
addi $s1,$s1,1
addi $s7,$s7,1
j loop4
loop5: # loop5 is to fill remaining element of temp in array
bgt $s0,$a0,doreturn
la $t0,temp
la $t2,arr
add $s7,$s7,$zero
mul $s0,$s0,4
mul $s7,$s7,4
add $t0,$t0,$s0
add $t2,$t2,$s7
div $s7,$s7,4
div $s0,$s0,4
lw $t4,($t0)
sw $t4,($t2)
addi $s0,$s0,1
addi $s7,$s7,1
j loop5
doreturn: #doreturn procedure return to the sort procedure
jr $ra
print: # print procedure help in printing sorted array
bgt $s0,14,exit
li $v0,1
lw $a0,($t0)
syscall
addi $t0,$t0,4
add $s0,$s0,1
li $v0,4 #sys call for printing string
la $a0,gap
syscall #executing system call in reg v0
j print
exit : # exit procedure help in exiting program safely
li $v0,10
syscall