Use most basic PYTHON3 knowledge to answer the question. 4. (2 pts) Consider the
ID: 3587477 • Letter: U
Question
Use most basic PYTHON3 knowledge to answer the question.
4. (2 pts) Consider the list [55, 24, 16, 13, 21, 44, 26, 31] which we want to sort using merge sort: Merge Sort Algorithm: 1. Sort the first half of the list 2. Sort the second half of the list. 3. Merge the two sorted halves to get a sorted list. (a) Show the first half of the list after step 1 is done. Show the second half of the list after step 2 is done (b) Show the merge process of step 3 using the lists from parts a and b by tracing this step as shown in the course slides/notes. @ @Mao1 22Explanation / Answer
Please find the basic PYTHON3 program to merge sort the list : [55,24,16,13,21,44,26,31]
def mergeSort(list):
print("Split ",list)
if len(list)>1:
mid = len(list)//2
FHalf = list[:mid]
SHalf = list[mid:]
mergeSort(FHalf)
mergeSort(SHalf)
x=0
y=0
z=0
while x < len(FHalf) and y < len(SHalf):
if FHalf[x] < SHalf[y]:
list[z]=FHalf[x]
x=x+1
else:
list[z]=SHalf[y]
y=y+1
z=z+1
while x < len(FHalf):
list[z]=FHalf[x]
x=x+1
z=z+1
while y < len(SHalf):
list[z]=SHalf[y]
y=y+1
z=z+1
print("Merge ",list)
list = [55,24,16,13,21,44,26,31]
mergeSort(list)
print(list)
a) The first half of the list after the completion of step 1 is [13, 16, 24, 55] , follow the steps below to get the first half of sorted list.
The second half of the list after the step 2 done is : [21, 26, 31, 44] , Follow the steps given below to get the sorted second half list .
b) The merge process of step 3 to merge two sorted lists [13,16,24,55] and [21,26,31,44] is given below :
[ 13,16, 24, 55] [ 21, 26, 31, 44 ]
Compare 13 and 21 , put the smallest number into the result list :
List : [13]
[16,24,55] [21,26,31,44]
Compare 16 and 21 , put the smallest into the result list :
List : [13, 16]
[24,55] [21,26,31,44]
Compare 24 and 21 , put the smallest into the result list :
List : [13 , 16, 21 ]
[24, 55 ] [26, 31 , 44 ]
Compare 24 and 26 , put the smallest into the result list :
List : [ 13, 16, 21 , 24 ]
[55] [ 26, 31 , 44 ]
Compare 26 and 55, put the smallest into the result list :
List : [ 13, 16, 21, 24, 26 ]
[55] [ 31, 44]
Compare 31 and 55 , put the smallest into the result list :
List : [13,16,21,24,26,31]
[55] [44]
Compare 44 and 55 , put the smallest into the result list and also the last number to the list :
List : [13,16,21,24,26,31,44,55]
Thus after the tracing process at step 3 the sorted merged list is obtained as [13,16,21,24,26,31,44,55]
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.