Merge Sort Interview Question Part 1

1. What is the average case complexity for merge sort algorithm
a.O(n) b.O(n*n) c.O(nlogn) d.O(logn)
Ans:c

2. What is the worst case complexity for merge sort algorithm
a.O(n) b.O(n*n) c.O(nlogn) d.O(logn)
Ans:c


3. What is the best case complexity for merge sort algorithm
a.O(n) b.O(n*n) c.O(nlogn) d.O(logn)
Ans:c

4. What is the output of merge sort after the 1st pass given the following sequence of numbers: 25 57 48 37 12 92 86 33
a. 48 25 37 12 57 86 33 92
b. 12 25 33 37 48 57 86 92
c.12 25 33 37 48 57 86 92
d. 25 57 37 48 12 92 33 86
Ans:d

5. What is the output of merge sort after the 2nd pass given the following sequence of numbers: 25 57 48 37 12 92 86 33
a. 48 25 37 12 57 86 33 92
b. 12 25 33 37 48 57 86 92
c.25 37 48 57 12 33 86 92
d. 25 57 37 48 12 92 33 86
Ans:c

6. What is the output of merge sort after the 3rd pass given the following sequence of numbers: 25 57 48 37 12 92 86 33
a. 12 25 33 37 48 57 86 92
b. 12 25 33 37 48 57 86 92
c.12 25 33 37 48 57 86 92
d. 25 57 37 48 12 92 33 86
Ans:a


7. In which cases are the time complexities same in merge sort?
a. Worst and Best
b. Best and Average
c. Worst and Average
d. Worst, average and Best
Ans:d

8.Total numbers of passes in merge sort of 'n' numbers is _______.
a.n
b.n-1
c.log(n)
d.nlogn
Ans:c


9.Merge sort is based on the divide and conquer strategy.it consists of the following steps
a. Divide,Recursive and Conquer
b. Divide and Conquer
c. Divide and Recursive
d. None of the above
Ans. a


10.Given two sorted lists of size m,n ,the number of comparisons needed in the worst case by the merge sort algorithm is
a.mn b.max(m,n) c.min(m,n) d.m+n-1
Ans:d
Each comparison puts 1 element in the final sorted array. So,in the worst case m+n-1 comparisons are needed.

11. Suppose the array A contains 14 elements as follows:
A = [66, 33, 40, 22, 55, 88, 60, 11, 80, 20, 50, 44, 77, 30]
How many Passes are required to sort the above array A using the Merge sort algorithm?
a. 3
b. 4
c. 5
d. 7
e. 14
Ans. c

12. If you are provided with two files whose contents are sorted and the requirement is to copy the contents of both the files into a third file which should be sorted. In this case which of the sorting techniques can be an appropriate one?
a.Selection sort
b.Bubble sort
c.Merge sort
d.insertion sort
Ans:c

13. The merge sort algorithm involves the following steps.
(i) Recursively sort the 1st and 2nd halves separately
(ii) Merge the two-sorted halves into a sorted group.
(iii) If the number of items to sort is 0 or 1, return.

Which is the correct order of instructions in merge sort algorithm?
(a) (i),(ii),(iii)
(b) (ii),(iii),(i)
(c) (iii),(ii),(i)
(d) (iii),(i),(ii)
Ans:d

14. What is the output of merge sort after the 1st pass given the following sequence of numbers : 3,41,52,26,38,57,9,49
a. 3,41,26,52,38,57,9,49
b. 3,41,52,26,38,57,9,49
c. 3,41,52,26,38,57,9,49
d. 3,41,38,26,52,9,49,57
Ans. a

15. What is the output of merge sort after the 2nd pass given the following sequence of numbers : 3,41,52,26,38,57,9,49
a. 3,26,41,52,38,9,49,57
b. 3,26,41,52,9,38,49,57
c. 3,26,38,9,49,57,41,52
d. 3,26,41,52,38,49,57,9
Ans. b