Part 2: Merge sort

Merge sort is another of the sorts we looked at in class and, like it's cousin quick sort, it's a recursive divide-and-conquer algorithm that works by dividing the list to be sorted into two smaller lists and applying the sort algorithm to each. Merge sort does this in the most obvious way: by simply taking the first and second halves of the list to be each sublist.



To ideas are central to merge sort:

1. That a list with a length of 1 or 0 is already "sorted", by whatever criteria one might care about. This ensures that eventually, the algorithm will have sorted lists (of length 1) to work with.
2. That it is possible to combine 2 sorted lists into one by comparing the first item in each list and adding the least first item to another list, which will be full when both starting lists are empty. This is the "merge" part of merge sort.

For an example of merge sort, consider the list  [6, 8, 1, 10, 7], which we will sort in non-descending order.

Remember that the general algorithm is:

1. Halve the list to be sorted.
2. Perform merge sort on both half-lists
3. Merge the half-lists and return the result

 [6, 8, 1, 10, 7]           First, we split the list. 

 [6, 8]  [1, 10, 7]    Then we sort the first list.

 [6, 8]        We split it...

 [6] [8]   ...and sort the first list,

 [6] [8]  which is of length 1, so it is already sorted

 [6]+[8]  The second is as well, so we are ready to merge these lists.

 [6, 8]        The first item in the first list is smaller than that of the second, so we add it to a new list. Then the first list is empty so we add the second list.

 [6, 8]  [1, 10, 7]   So now we have a sorted first list, so we apply merge sort to the second.

[1] [10, 7]   Since the algorithm here is the same, I've omitted the next annotations.

[1]

[10, 7]

[10]+[7]

[7, 10]

[1]+[7, 10]

[1, 7, 10]

[6, 8]+[1, 7, 10]    Now , 1<6, so...

[6, 8]+[7, 10]->[1...]      Now , 6<7, so...

[8]+[7, 10]->[1, 6...]      Now , 7<8, so...

[8]+[10]->[1, 6, 7...]      Now , 8<10, so...

[]+[10]->[1, 6, 7, 8...]     Now , the first list is empty so we have:

[1, 6, 7, 8, 10]      And now we're done, this is the sorted list.

Notice that we could have improved the algorithm by checking to see if each half-list is sorted before sorting it. This would have removed the need to perform the full algorithm on [6, 8].

Merge sort has O(nlgn) complexity; it must perform n comparisons to perform the merge operation, and it must merge as many times as it split the list. An n long list will be split lg(n) times, where lg() is the base 2 logarithm. 

Coming soon, the exciting conclusion: Quick sort!