Merge Sort Interview Question Part 2

16. Given the initial sequence : 3,41,52,26,38,57,9,49 ,at the last step in the merge sort .the sequences to be merged are
a.{ 3,26,52,41} and {38,49,57,9}
b.{ 3,26,41,52} and {9,38,49,57}
c. {3,9,41,52} and {26,38,49,57}
d. {3,9,26,38} and {41,49,52,57}
Ans. b

17. Mergesort makes two recursive calls. Which statement is true after these recursive calls finish, but before the merge step?
a. The array elements form a heap
b. Elements in each half of the array are sorted among themselves
c. Elements in the first half of the array are less than or equal to elements in the second half of the array
d. . Elements in the first half of the array are greater than or equal to elements in the second half of the array
Ans. b
18. Given the initial sequence: {85 24 63 47 17 31 96 50}, at the last step in the
merge sort, the sequences to be merged are:
a). {24 47 63 85} and {17 31 50 96}
b). {17 24 31 47} and {50 63 85 96}
c). {24 85} {47 63} {17 31} and {50 96}
d). {17 24 31 47 63 85 96} and {50}
e). depends on choice of pivot
Ans. a
19.On each iteration,the size of the sorted lists in a merge sort
a. doubles
b. halves
c.remains the same
d. increases 4 times
Ans. a
On each iteration, the size of the sorted lists doubles, form 1 to 2 to 4 to 8 to 16 ...to n.

20. What is the output of merge sort after the 1st pass given the following sequence of numbers: 12 13 1 5 7 9 11 14
a. 12 13 1 5 7 9 11 14
b. 1 5 12 13 7 9 11 14
c. 1 5 7 9 11 12 13 14
d. 1 5 7 9 12 13 11 14
Ans:a


21. What is the output of merge sort after the 2nd pass given the following sequence of numbers: 12 13 1 5 7 9 11 14
a. 12 13 1 5 7 9 11 14
b. 1 5 12 13 7 9 11 14
c. 1 5 7 9 11 12 13 14
d. 1 5 7 9 12 13 11 14
Ans:b

22. What is the output of merge sort after the 3rd pass given the following sequence of numbers: 12 13 1 5 7 9 11 14
a. 12 13 1 5 7 9 11 14
b. 1 5 12 13 7 9 11 14
c. 1 5 7 9 11 12 13 14
d. 1 5 7 9 12 13 11 14
Ans:c


23. In every pass, maximum number of comparisons in the merge sort is _________.
a.n-1
b.n
c.log n
d.n*n
Ans:a

24.What does the following pseudocode do?

function sort(m)
var list left, right
if length(m) ≤ 1
return m
else
middle = length(m) / 2
for each x in m up to middle
add x to left
for each x in m after middle
add x to right
left = sort(left)
right = sort(right)
result = app(left, right)
return result
end if
a. quick sort
b. selection sort
c. insertion sort
d. merge sort
Ans. d