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 strings, in which each list of strings is sorted. For instance, if the original list was (“the” “quick” “brown” “fox”), split() would return a list of three lists—(“the”), (“quick”), and (“brown” “fox”)—because the strings “brown” and “fox” are already in the correct order. The algorithm would work just as well if split() made lists of one element each, but splitting the list into already-sorted chunks makes the algorithm natural by reducing the amount of work left to do if the list is nearly sorted already. In the listing, the loop on lines 14–24 keeps processing as long as there are elements on the input list. Each time through the loop, line 16 makes a new list, and the loop on lines 17–22 keeps moving elements from the input list onto this list as long as they are in the correct order. When the loop runs out of elements on the input list or encounters two elements out of order, line 23 appends the current list to the output list of lists.

The function merge() takes two lists that are already sorted and merges them into a single sorted list. The loop on lines 37– 45 executes as long as there is something on both lists. The if statement on line 40 selects the smaller first element of the two lists and moves it to the output list. When one of the lists becomes empty, all the elements of the other list must be appended to the output list. Lines 46 and 47 concatenate the output list with the empty list and the non-empty list to complete the merge.

The function mergePairs() takes a list of lists of strings and calls merge() on each pair of lists of strings, replacing the original pair with the single merged list. The loop on lines 61–77 executes as long as there is something in the input list. The if statement on line 63 checks whether there are at least two lists of strings on the input list. If not, line 76 appends the odd list to the output list. If so, lines 65 and 66 remove the two lists, which are merged on lines 68 and 69. The new list is appended to the output list on line 72, and all the intermediate list nodes that were allocated are freed on lines 70, 71, and 73. Lines 72 and 73 remove the two lists that were merged from the input list.

The last function is sortStrings(), which performs the merge sort on an array of strings. Lines 88 and 89 put the strings into a list. Line 90 calls split() to break up the original list of strings into a list of lists of strings. The loop on lines 91 and 92 calls mergePairs() until there is only one list of strings on the list of lists of strings. Line 93 checks to ensure that the list isn’t empty (which is the case if the array has 0 elements in it to begin with) before removing the sorted list from the list of lists. Finally, lines 95 and 96 put the sorted strings back into the array. Note that sortStrings() does not free all the memory if allocated.

An implementation of a merge sort.