Merge Sort
A medium Sorting interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Sorting
- Sheets
- 3
- Core for
- 13 roles
The problem
Sort an array using the divide-and-conquer approach: split the array into halves, recursively sort each half, and merge the sorted halves.
Example 1
- Input
- nums = [38, 27, 43, 3, 9, 82, 10]
- Output
- [3, 9, 10, 27, 38, 43, 82]
Example 2
- Input
- nums = [5, 2, 3, 1]
- Output
- [1, 2, 3, 5]
Constraints
- 1 <= nums.length <= 5 * 10^4
- -10^5 <= nums[i] <= 10^5
How to think about it
Updated 2026-09-29Sorting two sorted lists together is effortless because the global minimum must be sitting at one of the two heads. By recursively halving down to trivial single-element slices, the problem reduces entirely to linear zip-merges across log n tree levels, providing guaranteed optimal time unaffected by initial order.
Approaches, worst first
Slice allocation recursion
time O(n log n) · space O(n log n)
Create new subarray slices at each recursive call and return merged new lists. Conceptually pure and idiomatic in functional programming, but creates heavy allocations and garbage collector pressure on large inputs.
Index recursion with scratch bufferWrite this one
time O(n log n) · space O(n)
Pass index ranges `[left, right]` down the recursion and merge into a single reusable helper array before copying back into the original range. Limits heap overhead to a single buffer while maintaining the stable comparison order.
Where people lose marks · 3
- Using `(left + right) / 2` without checking bounds can overflow standard integer types; `left + (right - left) / 2` avoids numerical overflow.
- Forgetting to copy the remaining elements from whichever half was not exhausted drops valid data when the other pointer reaches its boundary first.
- Using `<` instead of `<=` when picking from the left half breaks stability; tied elements must favor the left array to keep their original relative positioning.
The theory behind it
Sorting — the ground this problem stands on. All Sorting problems
What Sorting is
Sorting is the act of arranging a scrambled hand of playing cards into ascending rank from left to right. It reorganizes scattered data according to a consistent comparison rule, like numbering index cards or alphabetizing names. While unsorted data requires searching every single entry to verify whether an item exists, ordered data establishes predictable relationships that make duplicates, clusters, and extreme values immediately visible.
When to reach for it
Reach for sorting when a problem asks to group identical items, detect overlaps among intervals, find rank percentiles, or pair values matching a target sum. If an unordered problem appears intractable in polynomial time, sorting the input frequently unlocks linear scans or two-pointer sweeps. When an O(n log n) preprocessing step simplifies downstream matching logic, sorting is usually the right opening move.
How the pattern works
Think of sorting as a trade: invest logarithmic overhead upfront to make subsequent queries direct and orderly. Compare adjacent elements to uncover duplicate entries, or march inward from outer boundaries once elements stand in monotonic sequence. When designing custom comparators, confirm strict weak ordering by verifying reflexivity, antisymmetry, and transitivity; inconsistent comparison logic breaks internal pivot partitions or produces corrupted outputs.
More Sorting problems
Target Roles
Core requirement for 13 roles:
Asked at
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .