.data

original_list: .space 100

sorted_list: .space 100

str0: .asciiz "Enter size of list (between 1 and 25): "

str1: .asciiz "Enter one list element: "

str2: .asciiz "Content of list: "

str3: .asciiz "Enter a key to search for: "

strYes: .asciiz "Key found!"

strNo: .asciiz "Key not found!"

.text

#This is the main program.

#It first asks user to enter the size of a list.

#It then asks user to input the elements of the list, one at a time.

#It then calls printList to print out content of the list.

#It then calls inSort to perform insertion sort

#It then asks user to enter a search key and calls bSearch on the sorted list.

#It then prints out search result based on return value of bSearch

main:

addi $sp, $sp -8

sw $ra, 0($sp)

li $v0, 4

la $a0, str0

syscall

li $v0, 5 #Read size of list from user

syscall

move $s0, $v0

move $t0, $0

la $s1, original_list

loop_in:

li $v0, 4

la $a0, str1

syscall

sll $t1, $t0, 2

add $t1, $t1, $s1

li $v0, 5 #Read elements from user

syscall

sw $v0, 0($t1)

addi $t0, $t0, 1

bne $t0, $s0, loop_in

li $v0, 4

la $a0, str2

syscall

move $a0, $s1

move $a1, $s0

jal printList #Call print original list

jal inSort #Call inSort to perform insertion sort in original list

sw $v0, 4($sp)

li $v0, 4

la $a0, str2

syscall

lw $a0, 4($sp)

jal printList #Print sorted list

li $v0, 4

la $a0, str3

syscall

li $v0, 5 #Read search key from user

syscall

move $a2, $v0

lw $a0, 4($sp)

jal bSearch #Call bSearch to perform binary search

beq $v0, $0, notFound

li $v0, 4

la $a0, strYes

syscall

j end

notFound:

li $v0, 4

la $a0, strNo

syscall

end:

lw $ra, 0($sp)

addi $sp, $sp 8

li $v0, 10

syscall

#printList takes in a list and its size as arguments.

#It prints all the elements in one line.

printList:

#Your implementation of printList here

jr $ra

#inSort takes in a list and it size as arguments.

#It performs INSERTION sort in ascending order and returns a new sorted list

#You may use the pre-defined sorted_list to store the result

inSort:#Your implementation of inSort here

jr $ra

#bSearch takes in a list, its size, and a search key as arguments.

#It performs binary search RECURSIVELY to look for the search key.

#It will return a 1 if the key is found, or a 0 otherwise.

#Note: you MUST NOT use iterative approach in this function.

bSearch:#Your implementation of bSearch here

jr $ra

Need to write printList, insort, and bSearch

printList: It is a function to print out the content of a list. It takes ina listandits sizeas arguments. It does not return any value.

inSort:It performsInsertion Sortinascending orderon a list. It takes ina listandits sizeas arguments. It returns the sorted list as a new list. You may usesorted_listdefined in the data segment in this function.

bSearch:It performs arecursiveBinary Searchof a key on a list. It takes inalist,its size, anda search keyas arguments. It returns 1 if the key exists inthe list, otherwise it returns 0. You must implement this algorithmrecursively;therefore, be aware of the use of stack memory.

Sample example

Enter size of list (between 1 and 25): 8

Enter one list element: 8

Enter one list element: 7

Enter one list element: 6

Enter one list element: 5

Enter one list element: 4

Enter one list element: 3

Enter one list element: 2

Enter one list element:1

Content of list: 8 7 6 5 4 3 2 1

Content of list: 1 2 3 4 5 6 7 8

Enter a key to search for: 12

Key not found!

--program is finished running--