Merge Sort

Merge sort is a sorting algorithm that works in two phases: it splits the list into smaller and smaller pieces, then merges those pieces back together in order.

Splitting keeps halving the list until every sub-list holds a single item. A single item cannot be out of order, so every one-item list already counts as sorted — that is the starting point the merges work from.

Splitting

Each sub-list is halved again and again. When a sub-list has an odd number of items, one half simply takes the extra item. A list of six items, [34, 7, 51, 19, 8, 26], first becomes [34, 7, 51] and [19, 8, 26], then [34], [7, 51], [19] and [8, 26], and finally six lists that hold one item each.

Merging

Merging two sorted lists means comparing their front items and taking the smaller one into a new list. This repeats until one list is empty, then the remaining items of the other list are added to the end. Merging [7, 34, 51] with [8, 19, 26]:

Merging in order is what does the sorting — nothing is sorted afterwards. Because each list is already sorted, its front item is the smallest value it has left, so taking the smaller front item always drops the next smallest value into the right place.

Up to one list, and descending order

Merged lists are then merged with other merged lists: one-item lists form sorted pairs, pairs form larger sorted lists, and so on until a single sorted list remains. For descending order the splitting never changes; you simply take the larger front item at each comparison instead.