2. Here is the pseudo-code for MergeSort and Merge with some print statements added: function Merge Sort (arr, start, end) if start < end: print "HI" middle = (start+end) // 2 Merge Sort (arr, start, middle) MergeSort (arr, middle+1, end) Merge (arr, start, middle, middle+1, end) print (arr) end if end function function Merge (arr, starti, end1, start2, end2) temp array of same size as arr i start1; j = start2; k = start1 while i <= end1 and j <= end2: if arr[i] <= arr[j]: temp [k] = arr[i]; i++; k++ else: temp [k] = arr[j]; j++; k++ end if end while while i <= end1: temp [k] = arr[i]; i++; k++ end while while j <= end2: temp [k] = arr[j]; j++; k++ end while for i = start to end2 inclusive: print "HELLO" arr[i] = temp[i] end for end function (a) If we call MergeSort ([99,44,55,88,33,22,11] the print(arr) statement will run ex- [12 pts] actly 6 times. What will it print each time? First Time Second Time Third Time Fourth Time Fifth Time Sixth Time (b) When we run the code above on a list of length 7: [4 pts] Number of times HI will be output? Number of times HELLO will be output? (c) When we run the code above on a list of length 4*, how many times will HI be printed? [6 pts] Simplify your answer. Number of times HI will be output? (d) Explain your answer to (c) [10 pts] Solution:
2. Here is the pseudo-code for MergeSort and Merge with some print statements added: function Merge Sort (arr, start, end) if start < end: print "HI" middle = (start+end) // 2 Merge Sort (arr, start, middle) MergeSort (arr, middle+1, end) Merge (arr, start, middle, middle+1, end) print (arr) end if end function function Merge (arr, starti, end1, start2, end2) temp array of same size as arr i start1; j = start2; k = start1 while i <= end1 and j <= end2: if arr[i] <= arr[j]: temp [k] = arr[i]; i++; k++ else: temp [k] = arr[j]; j++; k++ end if end while while i <= end1: temp [k] = arr[i]; i++; k++ end while while j <= end2: temp [k] = arr[j]; j++; k++ end while for i = start to end2 inclusive: print "HELLO" arr[i] = temp[i] end for end function (a) If we call MergeSort ([99,44,55,88,33,22,11] the print(arr) statement will run ex- [12 pts] actly 6 times. What will it print each time? First Time Second Time Third Time Fourth Time Fifth Time Sixth Time (b) When we run the code above on a list of length 7: [4 pts] Number of times HI will be output? Number of times HELLO will be output? (c) When we run the code above on a list of length 4*, how many times will HI be printed? [6 pts] Simplify your answer. Number of times HI will be output? (d) Explain your answer to (c) [10 pts] Solution:
Related questions
Question
![2. Here is the pseudo-code for MergeSort and Merge with some print statements added:
function Merge Sort (arr, start, end)
if start < end:
print "HI"
middle = (start+end) // 2
Merge Sort (arr, start, middle)
MergeSort (arr, middle+1, end)
Merge (arr, start, middle, middle+1, end)
print (arr)
end if
end function
function Merge (arr, starti, end1, start2, end2)
temp array of same size as arr
i start1; j = start2; k = start1
while i <= end1 and j <= end2:
if arr[i] <= arr[j]:
temp [k] = arr[i]; i++; k++
else:
temp [k] = arr[j]; j++; k++
end if
end while
while i <= end1:
temp [k] = arr[i]; i++; k++
end while
while j <= end2:
temp [k] = arr[j]; j++; k++
end while
for i = start to end2 inclusive:
print "HELLO"
arr[i] = temp[i]
end for
end function
(a) If we call MergeSort ([99,44,55,88,33,22,11] the print(arr) statement will run ex- [12 pts]
actly 6 times. What will it print each time?
First Time
Second Time
Third Time
Fourth Time
Fifth Time
Sixth Time](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fe0394dda-1230-46f2-92ff-9edb879436e7%2F6662860c-8aba-44a9-9363-a3c75a16778b%2F5cowcc_processed.png&w=3840&q=75)
Transcribed Image Text:2. Here is the pseudo-code for MergeSort and Merge with some print statements added:
function Merge Sort (arr, start, end)
if start < end:
print "HI"
middle = (start+end) // 2
Merge Sort (arr, start, middle)
MergeSort (arr, middle+1, end)
Merge (arr, start, middle, middle+1, end)
print (arr)
end if
end function
function Merge (arr, starti, end1, start2, end2)
temp array of same size as arr
i start1; j = start2; k = start1
while i <= end1 and j <= end2:
if arr[i] <= arr[j]:
temp [k] = arr[i]; i++; k++
else:
temp [k] = arr[j]; j++; k++
end if
end while
while i <= end1:
temp [k] = arr[i]; i++; k++
end while
while j <= end2:
temp [k] = arr[j]; j++; k++
end while
for i = start to end2 inclusive:
print "HELLO"
arr[i] = temp[i]
end for
end function
(a) If we call MergeSort ([99,44,55,88,33,22,11] the print(arr) statement will run ex- [12 pts]
actly 6 times. What will it print each time?
First Time
Second Time
Third Time
Fourth Time
Fifth Time
Sixth Time
![(b) When we run the code above on a list of length 7:
[4 pts]
Number of times HI will be output?
Number of times HELLO will be output?
(c) When we run the code above on a list of length 4*, how many times will HI be printed? [6 pts]
Simplify your answer.
Number of times HI will be output?
(d) Explain your answer to (c)
[10 pts]
Solution:](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fe0394dda-1230-46f2-92ff-9edb879436e7%2F6662860c-8aba-44a9-9363-a3c75a16778b%2F59057u8_processed.png&w=3840&q=75)
Transcribed Image Text:(b) When we run the code above on a list of length 7:
[4 pts]
Number of times HI will be output?
Number of times HELLO will be output?
(c) When we run the code above on a list of length 4*, how many times will HI be printed? [6 pts]
Simplify your answer.
Number of times HI will be output?
(d) Explain your answer to (c)
[10 pts]
Solution:
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps
