Warning: The hard deadline has passed. You can attempt it, but you will not get credit for it. You are welcome to try it as a learning exercise.
To specify an array or sequence of values in an answer, separate the values inthe sequence by whitespace. For example, if the question asks for the firstten powers of two (starting at 1), then the following answer is acceptable: 1 2 4 8 16 32 64 128 256 512If you wish to discuss a particular question and answer in the forums, pleasepost the entire question and answer, including the seed (which can be used bythe course staff to uniquely identify the question) and the explanation (whichcontains the correct answer).
(seed = 822234)Give the array that results immediately after the 7th call (and return)from merge() when top-down mergesorting the following array of size 12: 65 56 31 83 30 17 99 92 42 29 73 48 Your answer should be a sequence of 12 integers, separated by whitespace.
(seed = 604518)The column on the left contains an input array of 12 strings to be sorted; the columnon the right contains the strings in sorted order; each of the other 4 columns contains thearray at some intermediate step during either top-down or bottom-up mergesort(with different columns potentially corresponding to different algorithms). pink drab drab drab iris drab iris fawn fawn fawn pink fawn kobi iris iris iris kobi flax puce kobi kobi kobi puce iris fawn pink navy pink drab kobi drab puce pear puce fawn leaf navy lime pink lime navy lime pear navy puce navy pear navy lime pear flax pear flax pear flax flax leaf flax lime pink plum leaf lime plum leaf plum leaf plum plum leaf plum puce ---- ---- ---- ---- ---- ---- 0 ? ? ? ? 3 Match up each column with the corresponding mergesorting algorithm from the given list: 0. Original input 1. Top-down Mergesort (standard recursive version) 2. Bottom-up Mergesort (nonrecursive version) 3. SortedYou should use each choice at least once. Your answer should be a sequence of 6 integersbetween 0 and 3 (starting with 0 and ending with 3), separated by whitespace.Hint: think about algorithm invariants. Do not trace code.
(seed = 330693)Which of the following statements about mergesort are true? Check all that apply. Unless otherwise specified, assume that mergesort refers to the pure recursive (top-down) version of mergesort (with no optimizations), using the merging subroutine described in lecture.
Any compare-based sorting algorithm requires at least lg (N!) compares (in the worst case) to sort an array of N items.
For any array of N distinct keys with N a power of 2, top-down mergesort and bottom-up mergesort compare exactly the same pairs of keys (but possibly in a different order).
Any two items are compared with one another no more than once during bottom-up mergesort.
Mergesort is a stable sorting algorithm.
Mergesort uses only a logarithmic amount of space (other than the input array).