Merge sort is a divide-and-conquer sorting method that splits a list into halves, sorts each half by the same procedure, and then merges the two sorted halves into one ordered list. The merging step repeatedly takes the smaller of the two leading items, which is why the combined result comes out in order.
Because the work of dividing and merging is the same regardless of the input, merge sort guarantees a running time on the order of n log n in all cases, not just on average. Knuth’s The Art of Computer Programming, Volume 3, “Sorting and Searching,” analyzes merging and merge-based sorts in depth and traces the idea of merging sorted runs to the earliest days of stored-program computing, including a 1945 description by John von Neumann.
Merge sort is naturally stable, meaning that items which compare as equal keep their original relative order, provided the merge step favors the earlier of two equal items. Stability makes it a common choice when records are sorted on several keys in turn.
The method is also the foundation of external sorting, the technique used when data is too large to fit in main memory. Sorted runs are written to and read from external storage such as tape or disk and merged in passes, an application that Knuth’s Volume 3 develops at length and that long predates the in-memory sorting most programmers see first.