Merge Sort: Split, Sort, Merge

Merging two already-sorted lists is easy: look at the front of each list, take the smaller front element, move it to the result, and repeat. Since both lists are sorted, the smallest remaining element is always sitting at one of the two fronts, so you never have to search. Merge sort builds on this by recursion. It splits the array in half, sorts each half by calling itself, then merges the two sorted halves using that simple two-pointer walk. A single element counts as already sorted, so the splitting stops there and the merging begins.

Each split cuts the problem size roughly in half, so an array of n elements needs about log2(n) levels of splitting before every piece is down to one element. At that bottom level there is nothing to do but merge pairs back up, level by level, until the whole array is one sorted list again. At each level, merging all the pieces together touches every element once, so the total work is proportional to n per level, times log2(n) levels, giving n log n overall.

That n log n growth is why merge sort pulls ahead of insertion sort on large arrays. Insertion sort shifts elements in place and avoids extra memory, but its worst-case work grows as n squared, since each new element can require sliding past many already-placed ones. Merge sort copies elements into new arrays at every merge step, which costs extra memory and overhead, but n log n grows so much slower than n squared that on large inputs the copying cost is outweighed many times over.