All the source code is contained in BinarySearch.s. This program creates a list of integers based on user inputs. Then it performs Insertion Sort on the list. Finally it searches for a user defined key using Binary Search. Your task is to implement 3 of the functions described below. Make sure you DO NOT modify the main method! In order to understand how arguments are passed to the following functions, study the main function CAREFULLY.

printList: It is a function to print out the content of a list. It takes in a list and its size as arguments. It does not return any value.

inSort: It performs Insertion Sort in ascending order on a list. It takes in a list and its size as arguments. It returns the sorted list as a new list. You may use sorted_list defined in the data segment in this function.

bSearch: It performs a recursive Binary Search of a key on a list. It takes in a list, its size, and a search key as arguments. It returns 1 if the key exists in the list, otherwise it returns 0. You must implement this algorithm recursively; therefore, be aware of the use of stack memory.

.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 original list: "

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

str4: .asciiz "Content of sorted list: "

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

move $a0, $s1

move $a1, $s0

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

sw $v0, 4($sp)

li $v0, 4

la $a0, str2

syscall

la $a0, original_list

move $a1, $s0

jal printList #Print original list

li $v0, 4

la $a0, str4

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 $a3, $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