The Merge Sort

The merge sort is a “divide and conquer” sort as well. It works by considering the data to be sorted as a sequence of already-sorted lists (in the worst case, each list is one element long). Adjacent sorted lists are merged into larger sorted lists until there is a single sorted list containing all the elements. The merge sort is good at sorting lists and other data structures that are not in arrays, and it can be used to sort things that don’t fit into memory. It also can be implemented as a stable sort. The merge sort was suggested by John von Neumann in 1945!

Below example shows an implementation of the merge sort algorithm. To make things more interesting, the strings will be put into a linked list structure rather than an array. In fact, the algorithm works better on data that is organized as lists, because elements in an array cannot be merged in place (some extra storage is required).

There are four functions that together implement merge sort. The function split() takes a list of strings and turns it into a list of lists of