Question

This question has three parts: a) binary search, b) selection sort, and c) merge sort.

a) Suppose we are performing a binary search on a sorted list called numbers initialized as follows:

#index 0 1 2 3 4 5 6 7 8 9 10 11 12 13

numbers = [-2, 0, 1, 7, 9, 16, 19, 28, 31, 40, 52, 68, 85, 99]

#search for the value 5

index = binary_search(numbers, 5)

Write the indexes of the elements that would be examined by the binary search (the mid values in our algorithm's code) and write the value that would be returned from the search. Assume that we are using the binary search algorithm shown in lecture and section.

Indexes examined :

Value returned :

b) Write the state of the elements of the list below after each of the first 3 passes of the outermost loop of the selection sort algorithm.

numbers = [63, 9, 45, 72, 27, 18, 54, 36]

selection_sort(numbers)

after pass 1 :

after pass 2 :

after pass 3 :

c) Trace the complete execution of the merge sort algorithm when called on the list below, similarly to the example trace of merge sort shown in the lecture slides. Show the sub-lists that are created by the algorithm and show the merging of sub-lists into larger sorted lists.

numbers = [63, 9, 45, 72, 27, 18, 54, 36]

merge_sort(numbers)

1st split :

2nd split :

3rd split :

1st merge :

2nd merge :

3rd merge :

Answer 1