Merge Sort
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.
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.
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.