Merge Sort Interview Questions and Answers: Traces, Complexity, and Code
Prepare crisp merge sort interview answers through a fully traced array, boundary-safe Java implementation, complexity proof, stability example, and inversion-count follow-up.
KnowledgeGate Team
Exam prep & CS education

A defensible merge sort interview answer needs more than divide and conquer: it needs a trace, a merge comparison, a complexity derivation, a stability proof, and boundary-safe code. The array [38,27,43,3,9,82,10] makes each claim concrete, with wider practice in the Coding & Skills placement route.
What is merge sort? Give the 30-second interview answer
“What is merge sort, and how does it work?”
Merge sort recursively splits a range until each subrange has at most one element, then merges adjacent sorted ranges with two pointers until the complete array is sorted. Its phases are divide, recursively conquer, and combine by merging.
For the standard array implementation, remember these properties:
Best, average, and worst-case time:
Theta(n log n)Temporary-array space:
Theta(n)Recursion depth:
Theta(log n)Stable when equal keys are taken from the left half first
Not the usual in-place choice for arrays
The DSA interview questions for placements guide organises the wider sequence. Merge sort's trace, proof, and implementation details follow.
Trace merge sort on [38, 27, 43, 3, 9, 82, 10]
Use half-open ranges [lo, hi), including lo but excluding hi. Split [0,7) into [0,3) containing [38,27,43] and [3,7) containing [3,9,82,10].
The complete downward split is:
[38,27,43]becomes[38]and[27,43], then[27,43]becomes[27]and[43].[3,9,82,10]becomes[3,9]and[82,10], then both pairs become singletons.
Now merge upward:
[27] + [43] -> [27,43], with 1 comparison.[38] + [27,43] -> [27,38,43], with 2 comparisons.[3] + [9] -> [3,9], with 1 comparison.[82] + [10] -> [10,82], with 1 comparison.[3,9] + [10,82] -> [3,9,10,82], with 2 comparisons.[27,38,43] + [3,9,10,82] -> [3,9,10,27,38,43,82], with 6 comparisons.
The exact total is 1 + 2 + 1 + 1 + 2 + 6 = 13 key comparisons.
In the final merge, compare 27:3 and emit 3; compare 27:9 and emit 9; compare 27:10 and emit 10. Then compare 27:82, 38:82, and 43:82, emitting 27, 38, and 43. The left half is exhausted, so append 82. That is six key comparisons but seven output writes. Comparisons and writes are different operations.
![Diagram shows a top-down split of [38,27,43,3,9,82,10] and bottom-up merges ending at [3,9,10,27,38,43,82], with 13 total comparisons.](https://cdn.knowledgegate.ai/blog-assets/blog_asset_1786690842122_ovzusb.jpg)
How does the merge step work, and why is it linear?
“Write the merge step.” A language-neutral version is:
merge(a, lo, mid, hi, temp):
i = lo
j = mid
k = lo
while i < mid and j < hi:
if a[i] <= a[j]:
temp[k] = a[i]
i = i + 1
else:
temp[k] = a[j]
j = j + 1
k = k + 1
copy a[i:mid] into temp starting at k
copy a[j:hi] into temp starting after that
copy temp[lo:hi] back into a[lo:hi]The <= deliberately chooses the left item on equal keys, preserving stability. Above, the pointers consume seven elements, make six key comparisons, emit 3,9,10,27,38,43, and append 82 after exhausting the left side.
Merging takes Theta(hi - lo) time because each element is read and written a constant number of times. Two non-empty ranges containing n elements require at most n - 1 key comparisons, not always exactly that many.
Why is merge sort O(n log n), and what space does it need?
“Derive the complexity instead of quoting it.” For balanced input, T(n) = 2T(n/2) + Theta(n). There are Theta(log n) levels, each processing Theta(n) elements across its merges, giving Theta(n log n).
Seven is not a power of two, so the trace has uneven branches of three and four elements. That changes neither the asymptotic number of levels nor the total work argument.
The baseline still splits and merges an already sorted array, so best-case time remains Theta(n log n), though some merges use fewer comparisons. The check a[mid - 1] <= a[mid] can skip an ordered merge but is an optimisation.
One reusable temporary array needs Theta(n) space. Recursive calls add Theta(log n) stack depth. See sorting algorithms comparison and complexity when you need to compare this stable, auxiliary-space approach with other sorts.
How do you code merge sort without off-by-one bugs?
Keep one convention throughout. This Java version uses half-open ranges and allocates the temporary array only once.
public final class MergeSort {
public static void sort(int[] a) {
int[] temp = new int[a.length];
sort(a, 0, a.length, temp);
}
private static void sort(int[] a, int lo, int hi, int[] temp) {
if (hi - lo <= 1) return;
int mid = lo + (hi - lo) / 2;
sort(a, lo, mid, temp);
sort(a, mid, hi, temp);
merge(a, lo, mid, hi, temp);
}
private static void merge(int[] a, int lo, int mid, int hi, int[] temp) {
int i = lo, j = mid, k = lo;
while (i < mid && j < hi) {
if (a[i] <= a[j]) temp[k++] = a[i++];
else temp[k++] = a[j++];
}
while (i < mid) temp[k++] = a[i++];
while (j < hi) temp[k++] = a[j++];
System.arraycopy(temp, lo, a, lo, hi - lo);
}
}Common defects include forgetting a leftover tail, mixing endpoint conventions, and copying the wrong temp portion. Test boundaries and duplicates: [] -> [], [5] -> [5], [1,2,3] -> [1,2,3], [4,3,2,1] -> [1,2,3,4], and [4,2,4,1] -> [1,2,4,4]. The main trace must produce [3,9,10,27,38,43,82].
Is merge sort stable? Prove it with duplicate records
“What does stable mean, and is merge sort stable?” A stable sort preserves the original relative order of records with equal keys.
Sort [(4,A),(2,B),(4,C),(1,D)] using only the number as the key. The sorted left half is [(2,B),(4,A)], and the sorted right half is [(1,D),(4,C)]. During the final merge, (4,A) eventually meets (4,C). Taking the left record on equality keeps A before C, producing [(1,D),(2,B),(4,A),(4,C)].
If < sends equality right, C can come first. The result [(1,D),(2,B),(4,C),(4,A)] is sorted but unstable. Stability matters when an earlier ordering must survive a later sort by another key.

What follow-up questions reveal real understanding?
Can merge sort count inversions?
Yes. In [2,4,1,3,5], the inversions are (2,1), (4,1), and (4,3), so the exact count is 3. During a merge, taking 1 before the remaining left values [2,4] adds 2; taking 3 before the remaining [4] adds 1. The modified algorithm remains Theta(n log n).
Is merge sort in-place?
The standard array version is not in-place because it uses Theta(n) auxiliary storage. Specialised in-place variants are substantially more complex. Linked-list merges can relink nodes without an n-element array, though recursive stack space may remain.
Interview depth varies by role and hiring drive. Use this sequence to move from trace and complexity to boundary-safe code, stability, space trade-offs, and inversion counting, rather than treating it as an employer-specific process.
The short version and the next practice step
Keep this five-point answer card:
Split ranges until each contains at most one element.
Merge sorted ranges with two pointers.
Standard running time is
Theta(n log n).Standard array workspace is
Theta(n).Stability requires taking the left item when keys are equal.
Reproduce the seven-value trace, code the half-open-range version, and solve the three-inversion example unaided. DSA using Java offers an interview-focused Java path, while Coding For Placements covers C, C++, Java, Python, and competitive coding.
For a final one-minute check, label the duplicate values in [6,3_A,8,3_B,2]. Predict [2,3_A,3_B,6,8], explain why 3_A stays before 3_B, and state the Theta(n log n) time and Theta(n) array-workspace costs.
Keep learning
Merge Sort MCQs: 12 Solved Questions with Explanations
Solve 12 Merge Sort MCQs from the KnowledgeGate question bank. Each answer explains the recurrence, comparison count, space cost, tracing method, or application being tested.
Divide and Conquer for GATE: Recurrence Analysis of Merge Sort, Quick Sort and Binary Search
Turn split, solve and combine into a recurrence, then solve the standard Merge Sort, Quick Sort and Binary Search cases without relying on memorised answers.
Optimal Merge Pattern Interview Questions and Answers: Greedy Proof, Min-Heap Trace and Code
Learn how to explain and implement Optimal Merge Pattern through one exact heap trace, a correctness proof, common traps and ten concise interview answers.
Selection Sort Explained: Step-by-Step Trace, Complexity and Exam Traps
Learn the invariant behind Selection Sort, trace every pass, derive its exact comparison count, and avoid common stability and swap-count traps.





