Merge Sort

Merge sort is a sorting algorithm that splits an array in half, sorts each half by calling itself, and merges the two sorted halves into one. Its work is all in the merge, a step that combines two sorted lists by comparing only their front items, and that step decides everything else about it: why it is stable, why it needs an extra buffer, and why it costs O(n log n) whatever order the input arrives in. The topic opens on the splits and merges of eight numbers, then walks through one merge with its two indices and the copy that finishes it. A gotcha shows how comparing with < instead of <= reorders records with equal keys, and the code card implements the sort in three languages with a single shared buffer. The topic then counts the work on each level to show why no input is faster than another, sorts a linked list by relinking its nodes, and closes with an exercise that merges two departure boards.