Merge sort: split the list, then merge it back in order

Binary search is fast, but only on sorted data. So we need a good way to sort. Simple methods, like repeatedly swapping neighbours that are out of order, are easy to write but slow down badly on large lists. Merge sort is a classic method that stays efficient as lists grow, and it is built on one neat idea: merging two lists that are already sorted is easy.