Merge Sort appears across GATE, ISRO, PSU CS recruitment and state teaching exams such as UP-LT and TPSC. The questions rarely stop at the definition. They test the recurrence, exact comparison count, space complexity, stability and pass-by-pass tracing. Linked lists and bottom-up merging add two important exceptions to the usual array-based analysis.
Merge Sort recurrence and core facts
Merge Sort splits an array into two halves, recursively sorts both halves, then merges them in one linear pass. Its recurrence is T(n) = 2T(n/2) + O(n): two half-size subproblems and O(n) merge work.
There are log2(n) halving levels. All merges at one level process n elements in total, so every level costs O(n). Therefore, total work is O(n) x log2(n) = O(n log n). This is the best, average and worst-case time because the split does not depend on the input order.
Remember four facts: time is O(n log n) in every case; array implementations need O(n) auxiliary merge space; merging sorted lists of sizes m and n needs at most m + n - 1 comparisons; Merge Sort is stable and uses divide and conquer. See how these facts compare with quicksort, heapsort and others in Sorting Algorithms: Complexity and Comparison.
Time complexity: familiar questions and the scaling trap
Question 1: worst-case notation
"What is the time complexity of Merge Sort in the worst case?"
Options: (a) O(n) (b) O(n log n) (c) O(n^2) (d) O(log n)
Correct option: (b) O(n log n). The recurrence gives O(n) work at each of log2(n) levels. Unlike quicksort, Merge Sort always splits in the middle, so it never degrades to O(n^2). O(log n) is binary search's cost. Practise this one.
Question 2: average and worst cases
"The average-case and worst-case complexities of the Merge Sort algorithm are:"
Options: (a) O(n^2), O(n^2) (b) O(n^2), O(n log2 n) (c) O(n log2 n), O(n^2) (d) O(n log2 n), O(n log2 n)
Correct option: (d) O(n log2 n), O(n log2 n). Input order does not change the split tree or merge work. Quicksort, by contrast, averages O(n log n) but can reach O(n^2). Open the full solution.
Question 3: scaling n log n
"Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?"
Options: (a) 256 (b) 512 (c) 1024 (d) 2048
Correct option: (b) 512. Model time as t = c x n x log2(n).
For n = 64, log2(64) = 6, so 64 x 6 = 384 work units take 30 seconds. Thus c = 30 / 384 = 0.078125 seconds per unit.
Six minutes is 360 seconds. The available work is 360 / 0.078125 = 4608 units.
For 512, log2(512) = 9 and 512 x 9 = 4608 exactly.
Check: 256 x 8 = 2048 units, or 160 seconds. Meanwhile, 1024 x 10 = 10240 units, or 800 seconds. Thus 512 is the largest listed input that fits.
Naming the paradigm: divide and conquer
Question 4: the design technique
"Which of the following algorithm design technique is used in merge sort?"
Options: (a) Greedy method (b) Backtracking (c) Dynamic programming (d) Divide and Conquer
Correct option: (d) Divide and Conquer. Divide means splitting at the midpoint. Conquer means recursively sorting both halves. Combine means merging the sorted halves. Dynamic programming solves overlapping subproblems and reuses their answers. Merge Sort's halves are disjoint and each is solved once, so there is nothing to memoise. Wording such as "design approach" or "paradigm" does not change the answer. Open the full solution.
Space and the merge step: where marks quietly leak
Question 5: auxiliary space
"What is the auxiliary space complexity of merge sort?"
Options: (a) O(1) (b) O(log n) (c) O(n) (d) O(n log n)
Correct option: (c) O(n). The temporary merge array can hold n elements. It dominates the O(log n) recursion stack, so array-based Merge Sort is not in-place. Practise this one.
Question 6: asymptotic merge cost
"For merging two sorted lists of sizes m and n into a sorted list of size m + n, how many comparisons are required?"
Options: (a) O(m) (b) O(n) (c) O(log m + log n) (d) O(m + n)
Correct option: (d) O(m + n). Two pointers scan the lists; each comparison places an element and advances a pointer. The total is Theta(m + n), linear rather than logarithmic. Open the full solution.
Question 7: exact worst-case merge count
"Given two sorted list of size 'm' and 'n' respectively. The number of comparisons needed in the worst case by the merge sort algorithm will be"
Options: (a) m x n (b) maximum of m, n (c) minimum of m, n (d) m + n - 1
Correct option: (d) m + n - 1. In the worst case, the lists interleave. Each comparison outputs one element. After m + n - 1 comparisons, one element remains and needs no comparison. The asymptotic cost is Theta(m + n). Practise this one.
Merge Sort against the field
Question 8: the worst-case guarantee
"Which of the following sorting algorithms has the best time complexity in the worst case?"
Options: (a) Quick Sort (b) Merge Sort (c) Bubble Sort (d) Selection Sort
Correct option: (b) Merge Sort. It guarantees O(n log n). Quicksort can degrade to O(n^2), while Bubble Sort and Selection Sort are O(n^2) in the worst case. Open the full solution.
Question 9: sorting a singly linked list
"Which sorting algorithm is most suitable for sorting a singly linked list in ascending order in terms of both time and space complexity?"
Options: (a) Heap Sort (b) Merge Sort (c) Quick Sort (d) Bubble Sort
Correct option: (b) Merge Sort. Pointer relinking makes the merge use O(1) extra space instead of an O(n) array. A bottom-up implementation also avoids the recursion stack. Heapsort and typical quicksort need random access, which a singly linked list does not provide cheaply. We build this merge in DSA using Java. Practise this one.
Tracing the passes by hand
Question 10: the array after the second pass
"If one uses a straight two-way merge sort algorithm to sort the following elements in ascending order: 20, 47, 15, 8, 9, 4, 40, 30, 12, 17 then the order of these elements after the second pass of the algorithm is:"
Options:
(a) 8, 9, 15, 20, 47, 4, 12, 17, 30, 40
(b) 8, 15, 20, 47, 4, 9, 30, 40, 12, 17
(c) 15, 20, 47, 4, 8, 9, 12, 30, 40, 17
(d) 4, 8, 9, 15, 20, 47, 12, 17, 30, 40
Correct option: (b) 8, 15, 20, 47, 4, 9, 30, 40, 12, 17. Trace the runs, not the final sorted array.
Start: 20 | 47 | 15 | 8 | 9 | 4 | 40 | 30 | 12 | 17.
Pass 1: merge adjacent singletons: 20,47 | 8,15 | 4,9 | 30,40 | 12,17.
Pass 2: [20,47] with [8,15] becomes [8,15,20,47]. [4,9] with [30,40] becomes [4,9,30,40]. The unpaired [12,17] stays.
The result is 8,15,20,47, 4,9,30,40, 12,17, which is option (b).
Option (d) sorts too far. The question stops after Pass 2, not after the final merge. Open the full solution.
The tricky two: no recursion and many lists
Question 11: the recursion-free variant
"Which option names a non-recursive variant of Merge Sort?"
Options: (a) Quick sort (b) Merge sort (c) Heap sort (d) Bottom-up merge sort
Correct option: (d) Bottom-up merge sort. Top-down Merge Sort recursively sorts each half. The bottom-up variant loops over runs of size 1, 2, 4, 8 and so on. It retains O(n log n) time but removes recursive calls and the call stack. Practise this one.
Question 12: merging ceil(log n) sorted lists
"Suppose there are ceil(log n) sorted lists of floor(n / log n) elements each. The time complexity of producing a sorted list of all these elements is"
Options: (a) O(n log log n) (b) Theta(n log n) (c) Omega(n log n) (d) Omega(n^(3/2))
Correct option: (a) O(n log log n). Let k = ceil(log n). The lists hold about n elements in total. Keep their heads in a min-heap of size k. About n extract-and-insert steps each cost O(log k). Since k is about log n, log k = log log n. Total time is O(n log log n). This requires a heap-based k-way merge. Open the full solution.
Merge Sort essentials and further practice
Keep this memory card: T(n) = 2T(n/2) + O(n), giving O(n log n) in every case. Array merging needs O(n) auxiliary space. Linked-list merging needs O(1) extra space, and a bottom-up list implementation avoids the call stack. Merging lists of sizes m and n takes at most m + n - 1 comparisons. Merge Sort is stable and divide and conquer.
About 45 Merge Sort questions are available for continued practice. Open any linked question above and continue through the set. For complete algorithms preparation, use GATE Guidance by Sanchit Sir. For a broader question set, continue with Data Structures MCQs, or explore the MCQ Practice hub.
