Merge sort

Merge sort is a sort algorithm for lists (or any other data structure that can only be accessed sequentially, e.g. file streams) into a specified order. It is a particularly good example of the divide and conquer algorithmic paradigm.

Conceptually, merge sort works as follows:

If the list to be sorted is longer than one item:

1. Divide the unsorted list into two sublists of about half the size

1. Sort each of the two sublists

1. Merge the two sorted sublists back into one sorted list.

Merge sort has an average and worst-case performance of O(n log(n)). This means that it often needs to make fewer comparisons than quicksort. However, the algorithm's overhead is slightly higher than quicksort's, and, depending on the data structure to be sorted, may take more memory (though this is becoming less and less of a consideration). It is also much more efficient than quicksort if the data to be sorted can only be efficiently accessed sequentially, and is thus popular in languages such as LISP where sequentially accessed data structures are very common. Merge sort is a stable sort.

Mergesort is so sequential that it's practical to run it on tapes if you have four tape drives. It works as follows:

1. divide the data to be sorted in half and put half on each of two tapes

1. merge individual pairs of records from the two tapes; write two-record chunks alternately to each of the two output tapes

1. merge the two-record chunks from the two output tapes into four-record chunks; write these alternately to the original two input tapes

1. merge the four-record chunks into eight-record chunks; write these alternately to the original two output tapes

1. repeat until you have one chunk containing all the data, sorted --- that is, for lg n passes, where n is the number of records.

On tape drives that can run both backwards and forwards, you can run merge passes in both directions, avoiding any time rewinding.

This might seem to be of historical interest only, but on modern computers, locality of reference is of paramount importance in software optimization, because we have deep memory hierarchies. This might change if fast memory becomes very cheap again, or if exotic architectures like the Tera MTA become commonplace.