merge_insert_sort.asm

	.text
main:
	# Print string msg1
	li	$v0,4		# print_string syscall code = 4
	la	$a0, msg1	# load the address of msg
	syscall

	# Get input n from user and save
	li	$v0,5		# read_int syscall code = 5
	syscall	
	sw	$v0, n		# syscall results returned in $v0

	# Print string msg2
	li	$v0,4		# print_string syscall code = 4
	la	$a0, msg2	# load the address of msg2
	syscall

	# Get input a from user and save
	li	$v0,5		# read_int syscall code = 5
	syscall	
	sw	$v0, a		# syscall results returned in $v0

	# Print string msg3
	li	$v0,4		# print_string syscall code = 4
	la	$a0, msg3	# load the address of msg2
	syscall

	# Get input r from user and save
	li	$v0,5		# read_int syscall code = 5
	syscall	
	sw	$v0, r		# syscall results returned in $v0

# Generate the GP series
	li 	$t4, 1		# loop var, i
	la 	$a0, arr	# first elem as a0
	lw 	$t0, n
	lw 	$t1, a
	lw 	$t2, r

	sw   	$t1, ($a0)
	add 	$a0, $a0, 4	# addr of next elem
forloop:
	bge  	$t4, $t0, end_forloop
	mult 	$t1, $t2	# a *= r;
	mflo 	$t1
	sw   	$t1, ($a0)
	add 	$a0, $a0, 4	# addr of next elem
	add	$t4, $t4, 1	# increment i 
	b 	forloop
end_forloop:

# Print the series generated
	# Print string msg4
	li	$v0, 4
	la	$a0, msg4
	syscall

	li 	$t4, 0		# loop var, i
	la 	$a1, arr	# first elem as a1
	lw 	$t0, n

forloop1:
	bge  	$t4, $t0, end_forloop1
	li	$v0,1		# print_int syscall code = 1
	lw 	$a0, ($a1)
	syscall
	add 	$a1, $a1, 4	# next addr of elem
	add	$t4, $t4, 1	# increment i 
	# Print space
	li	$v0,4		# print_string syscall code = 4
	la	$a0, one_space
	syscall

	b 	forloop1
end_forloop1:

# reverse the array and store to desc
	li 	$t4, 0
	la      $a1, arr
	la	$a2, desc
	sll	$t3, $t0, 2	# end addr of arr
	add	$a1, $a1, $t3
	add	$a1, $a1, -4
forloop2:
	bge     $t4, $t0, end_forloop2
	lw 	$a0, ($a1)
	sw 	$a0, ($a2)

	add	$a1, $a1, -4
	add	$a2, $a2, 4
	add	$t4, $t4, 1

	b	forloop2
end_forloop2:

	# Print \n
	li	$v0,4		# print_string syscall code = 4
	la	$a0, newline
	syscall

# print descending array
	# Print string msg5
	li	$v0, 4
	la	$a0, msg5
	syscall

	li 	$t4, 0		# loop var, i
	la 	$a1, desc	# first elem as a1

forloop3:
	bge  	$t4, $t0, end_forloop3
	li	$v0,1		# print_int syscall code = 1
	lw 	$a0, ($a1)
	syscall
	add 	$a1, $a1, 4	# next addr of elem
	add	$t4, $t4, 1	# increment i 
	# Print space
	li	$v0,4		# print_string syscall code = 4
	la	$a0, one_space
	syscall

	b 	forloop3
end_forloop3:

# Sorting 

# (1) Insertion sort
	
insertion_sort:

	li $v0, 1
	lw $a3, n
	sub $a3, $a3, 1
	la $t0, desc
while_loop: 
	bgt $v0, $a3, end_while
	sub $v1, $v0, 1
	mul $a2, $v0, 4 
	add $a2, $t0, $a2
	lw $a0, 0($a2)
while_loop2: 
	blt $v1, 0, end_while2
	mul $a2, $v1, 4
	add $a2, $t0, $a2
	lw $a1, 0($a2)
	ble $a1, $a0, end_while2
	sw $a1, 4($a2)
	sub $v1, $v1, 1
	j while_loop2
end_while2:

	mul $a2, $v1, 4
	add $a2, $t0, $a2
	sw $a0, 4($a2)
	addi $v0, $v0, 1
j while_loop

end_while:
end_insertion_sort:

# print array after sorting
	# Print \n
	li	$v0,4		# print_string syscall code = 4
	la	$a0, newline
	syscall

	# Print string 
	li	$v0, 4
	la	$a0, msgsortedarray
	syscall

	li 	$t4, 0		# loop var, i
	la 	$t1, desc	# first elem as t1
	lw 	$t0, n
	lw 	$t2, r

forloop5:
	bge  	$t4, $t0, end_forloop5
	li	$v0,1		# print_int syscall code = 1
	lw 	$a0, ($t1)
	syscall
	add 	$t1, $t1, 4	# next addr of elem
	add	$t4, $t4, 1	# increment i 
	# Print space
	li	$v0,4		# print_string syscall code = 4
	la	$a0, one_space
	syscall

	b 	forloop5
end_forloop5:

# (2) Merge sort
merge_sort:

	la	$a1, desc
	la	$a2, temp

	li 	$t1, 0
	lw	$t2, n
addr_loop: 
	bge $t1, $t2, end_addr_loop
	
	move $t5, $a1
	sw $t5, ($a2)

	add $t1, $t1, 1
	add $a2, $a2, 4
	add $a1, $a1, 4
	b addr_loop

end_addr_loop:


	la	$a0, temp		# start of temp
	la	$a0, ($a0)		# start addr
	lw	$t0, n			# array lenght
	sll	$t0, $t0, 2		# or adding 4 (word)
	add	$a1, $a0, $t0		# find end address
	jal	mergesort		
  	b	sortend			
mergesort:
	addi	$sp, $sp, -16		
	sw	$ra, 0($sp)		
	sw	$a0, 4($sp)		
	sw	$a1, 8($sp)		
	
	sub 	$t0, $a1, $a0

	ble	$t0, 4, mergesortend
	
	srl	$t0, $t0, 3		# divide by 8
	sll	$t0, $t0, 2		
	add	$a1, $a0, $t0		# mid of array
	sw	$a1, 12($sp)		
	
	jal	mergesort		
	
	lw	$a0, 12($sp)		
	lw	$a1, 8($sp)		
	
	jal	mergesort		
	
	lw	$a0, 4($sp)		
	lw	$a1, 12($sp)		
	lw	$a2, 8($sp)		
	
	jal	merge			
	
mergesortend:				

	lw	$ra, 0($sp)		
	addi	$sp, $sp, 16		
	jr	$ra			
	
merge:
	addi	$sp, $sp, -16		
	sw	$ra, 0($sp)		
	sw	$a0, 4($sp)		
	sw	$a1, 8($sp)		
	sw	$a2, 12($sp)		
	
	move	$s0, $a0		
	move	$s1, $a1		
	
mergeloop:

	lw	$t0, 0($s0)		
	lw	$t1, 0($s1)		
	lw	$t0, 0($t0)		
	lw	$t1, 0($t1)		
	
	bgt	$t1, $t0, noshift	
	
	move	$a0, $s1		
	move	$a1, $s0		
	jal	shift			
	
	addi	$s1, $s1, 4		
noshift:
	addi	$s0, $s0, 4		
	
	lw	$a2, 12($sp)		
	bge	$s0, $a2, mergeloopend	
	bge	$s1, $a2, mergeloopend	
	b	mergeloop
	
mergeloopend:
	
	lw	$ra, 0($sp)		
	addi	$sp, $sp, 16		
	jr 	$ra			

shift:
	li	$t0, 10
	ble	$a0, $a1, shiftend	
	addi	$t6, $a0, -4		
	lw	$t7, 0($a0)		
	lw	$t8, 0($t6)		
	sw	$t7, 0($t6)		
	sw	$t8, 0($a0)		
	move	$a0, $t6		
	b 	shift			
shiftend:
	jr	$ra			
	
sortend:				

# Print array
	# Print \n
	li	$v0,4		# print_string syscall code = 4
	la	$a0, newline
	syscall

	# Print string 
	li	$v0, 4
	la	$a0, msgsortedarray1
	syscall

	li	$t0, 0				
loop1:
	lw	$t1, n			
	bge	$t0, $t1, end_loop1	
	sll	$t2, $t0, 2	
	lw	$t3, temp($t2)	
	lw	$a0, 0($t3)	
	li	$v0, 1		
	syscall			
	la	$a0, one_space	
	li	$v0, 4		
	syscall			
	add	$t0, $t0, 1	
	b	loop1
end_loop1:				
exit:
	# Print \n
	li	$v0,4		# print_string syscall code = 4
	la	$a0, newline
	syscall

	li	$v0,10		# exit
	syscall

	# Start .data segment (data!)
	.data
msg1:	.asciiz	"Enter n:   "
msg2:	.asciiz	"Enter a:   "
msg3:	.asciiz	"Enter r:   "
msg4:	.asciiz	"Ascending: "
msg5:	.asciiz	"Descending: "
msgsortedarray:	.asciiz	"Sorted Array using Insertion sort: "
msgsortedarray1:.asciiz	"Sorted Array using merge sort: "
newline:   .asciiz	"\n"
one_space: .asciiz	" "
arr: 	.word 0:100
desc: 	.word 0:100
n: 	.word 0
a: 	.word 0
r: 	.word 0
temp:	.word 0