DSA interview question

Merge Sort

Medium · Algorithms · Topics: sorting, divide and conquer, recursion

The problem

A logistics company needs to sort millions of delivery records by timestamp every night, and the result must be stable: records with the same timestamp have to keep their original order, because downstream systems depend on it. The O(n²) sorts are far too slow at this scale. Merge sort guarantees O(n log n) in every case and is stable. Its idea is divide and conquer: split the array in half, sort each half recursively, and merge the two sorted halves in linear time. The same merge step also powers external sorting, linked-list sorting and inversion counting.

Example: [38, 27, 43, 3, 9, 82, 10] → [3, 9, 10, 27, 38, 43, 82].

Function signature

void mergeSort(vector<int>& a);  // sorts a in non-decreasing order

Test cases

Input `a`	Output	Explanation
`[38, 27, 43, 3, 9, 82, 10]`	`[3, 9, 10, 27, 38, 43, 82]`	Odd length: halves of 3 and 4
`[5, 2, 9, 1, 5, 6]`	`[1, 2, 5, 5, 6, 9]`	Stable: equal elements keep their order
`[3, -1, 0, -7]`	`[-7, -1, 0, 3]`
`[1, 2, 3, 4]`	`[1, 2, 3, 4]`	Still O(n log n) on sorted input
`[42]`	`[42]`	Base case
`[]`	`[]`

(Confirm: non-decreasing order; O(n) extra memory is acceptable; the code also cross-checks 1,000 random arrays against std::sort.)

How interviewers phrase it

"Implement merge sort."
"Sort a linked list in O(n log n)" (merge sort is the standard answer).
"Count inversions in an array" or "count reverse pairs" (both are merge sort with extra counting in the merge step).
Theory: "Merge sort vs quick sort?"

Clarifying questions to ask

Is O(n) extra space acceptable?
Does stability matter?
Is the input an array or a linked list?
How large is n?

Follow-ups to expect

"Why is it O(n log n)?"
"Why is it stable?"
"What's its space complexity?"
"Merge sort vs quick sort?"
"How do you compute mid safely?"
"Can it be done without recursion?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview