Problem Statement
Merge Sort
Merge Sort is a way to sort a list by splitting it into smaller and smaller pieces until each piece is tiny, then carefully joining the pieces back together in order. Think of sorting a big pile of test papers: instead of sorting all of them at once, you split the pile in half, hand each half to a friend to sort, and then the two of you merge your sorted stacks into one sorted stack. This idea of "split the work, then combine the results" is called divide and conquer. Merge Sort always takes O(n log n) time, no matter what order the list starts in, and it is stable, which means equal items keep their original order relative to each other. That stability makes it a good pick when order among ties matters, and it works especially well on linked lists. The cost is that it usually needs some extra scratch space to do the merging.
Signals to notice
Brute force first
compare it to simpler sorts that keep fixing one local inversion at a time. That comparison is useful because it shows what merge sort refuses to do: it steps back, splits the problem into calmer pieces, and rebuilds order from clean halves instead of constantly patching the full array.
The key insight
if two halves are already sorted, combining them is calm and predictable. So the real job is to keep breaking the array into smaller sorted halves, then merge them back together with two pointers. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.
Trace it on arr=[5, 2, 4, 7, 1, 3, 2, 6]
Split at mid=4: left=[5,2,4,7], right=[1,3,2,6] Recurse left [5,2,4,7]: -> [5,2] sorts to [2,5], [4,7] stays [4,7], merge -> [2,4,5,7] Recurse right [1,3,2,6]: -> [1,3] stays [1,3], [2,6] stays [2,6], merge -> [1,2,3,6] Merge [2,4,5,7] & [1,2,3,6]: 2>1 take 1; 2<=2 take left 2 (stable); take 2; 4>3 take 3; take 4,5,6,7 result=[1,2,2,3,4,5,6,7] — left's 2 placed before right's 2 Return [1, 2, 2, 3, 4, 5, 6, 7]
What must stay true
every recursive call returns a sorted half, and the merge step never has to guess beyond the front of those halves. Because each level only combines already-sorted pieces, the whole algorithm stays orderly from the bottom up. As long as that statement keeps holding, you can trust the steps built on top of it.
Shape of the loop
function mergeSort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left = mergeSort(arr[:mid]) right = mergeSort(arr[mid:]) return merge(left, right) # two-pointer: take smaller front, <= keeps stability
Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
seeing merge as a pile of pointer bookkeeping instead of a promise about order. The moment both halves are sorted, you only ever compare their front elements, take the smaller one, and move forward. Most mistakes here are not about syntax; they come from losing track of what your state, pointer, or structure is supposed to mean.