Merge Sort Algorithm Java | Fresher Interview
Fast recall
Quick revision
Core answer
Whether you can explain the divide-merge structure and why it's guaranteed O(n log n) (unlike quicksort)
Thinking merge sort is in-place, or not explaining the log n levels x O(n) merge = O(n log n)
Tie the guarantee to balanced halving (always log n levels) and note the O(n) space tradeoff
Interview-ready guide
Interview answer
Merge sort is the classic divide-and-conquer sorting algorithm, and it has three phases.
First, divide: I split the array into two halves. Second, conquer: I recursively sort each half. Third, combine: I merge the two sorted halves into a single sorted array, by repeatedly comparing the front elements of each half and taking the smaller one.
The reason it's always O of n log n, in the best, average, and worst case, comes from two parts. The splitting always cuts the array in half, so the recursion has log n levels, that's how many times you can halve n down to one. Then, at each level, merging all the pieces back together touches every element exactly once, which is O of n work per level.
Multiply the log n levels by the O of n merge work per level and you get O of n log n. The key point is that this halving doesn't depend on the data at all, unlike quicksort, where a bad pivot can produce unbalanced partitions and an O of n squared worst case. Merge sort has no such failure mode, which is why its bound is guaranteed.
The tradeoff is space: the merge step needs a temporary buffer, so merge sort uses O of n auxiliary space and is not in place. It's also stable, as long as I use a less-than-or-equal comparison when merging, so equal elements keep their order.
And because it only needs sequential access, it's an excellent choice for sorting linked lists and for external sorting of data that doesn't fit in memory.
For example, [5, 2, 4, 1] splits into [5, 2] and [4, 1]. Those halves become [2, 5] and [1, 4], and the final merge produces [1, 2, 4, 5].
Merge Sort Algorithm Java | Fresher Interview
Direct Answer
Merge sort is divide-and-conquer: split the array in half, recursively sort each half, then merge the two sorted halves into one. It's O(n log n) in every case - log n levels of splitting, O(n) work to merge each level - regardless of input order. The cost is O(n) extra space for the merge. It's also stable.
Deep Dive & Architecture
Merge sort divides the array until each piece has one element, then merges neighboring sorted pieces. A merge compares the front values and copies the smaller one, so two sorted halves become one sorted range.
Worked example: [5, 2, 4, 1]
Split it into [5, 2] and [4, 1], then into single values. Merge to get [2, 5] and [1, 4]. The final merge compares 2 with 1, then 2 with 4, then 5 with 4, producing [1, 2, 4, 5].
The recursion tree has log n levels because every split halves the range. At any one level, the merge operations together read and write all n elements. Multiplying n work per level by log n levels gives O(n log n) in the best, average, and worst cases; input order does not remove the merge levels.
For arrays, the usual implementation needs an O(n) temporary buffer, and recursive calls use O(log n) stack depth. Taking from the left half when equal values are compared makes it stable. Merge sort is therefore attractive when stable, predictable time matters, but its extra array memory is a real trade-off.
Code Example
void mergeSort(int[] a, int lo, int hi) {
if (lo >= hi) return; // base: 0 or 1 element
int mid = lo + (hi - lo) / 2;
mergeSort(a, lo, mid); // sort left
mergeSort(a, mid + 1, hi); // sort right
merge(a, lo, mid, hi); // combine
}
void merge(int[] a, int lo, int mid, int hi) {
int[] tmp = new int[hi - lo + 1]; // O(n) buffer
int i = lo, j = mid + 1, k = 0;
while (i <= mid && j <= hi)
tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++]; // <= keeps it stable
while (i <= mid) tmp[k++] = a[i++];
while (j <= hi) tmp[k++] = a[j++];
System.arraycopy(tmp, 0, a, lo, tmp.length);
}
// {5,2,4,1}: split->{5,2}{4,1}->sort->{2,5}{1,4}->merge->{1,2,4,5}
Common Mistakes & Pitfalls
- 'In-place': merge sort needs O(n) auxiliary space for the merge buffer.
- Not explaining the guarantee: it's log n levels x O(n) merge = O(n log n), data-independent.
- Using
<in merge: use<=to keep it stable. - Off-by-one in indices:
mid = lo + (hi-lo)/2, recurse[lo,mid]and[mid+1,hi].
Check your understanding
Answer these without looking back at the article.
- What are the time complexities of common sorting algorithms?
- How does bubble sort work and when would you actually use it?
- What sorting algorithm does Java use internally in Arrays.sort()?
Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.