Merge sort variations

(1) There are at least three major variations for merge sorting, bottom up, top down, and sidewise.

In bottom up you merge successive pairs of sorted runs in each pass. Usually this is done with initial run lengths of 1. Bottom up does not require auxilliary storage for the recursion. The advantage of bottom up is that it doesn’t require auxilliary storage for the algorithm (ignoring space needed for merging).

In top down you divide the data into two equal sets, sort each, and merge them. Top down does require theta(log n) space for recursion. The advantage of top down is that it is absurdly simple.

In sidewise you incrementally consume data, building a sequence of sorted runs of decreasing size, and merging a run with its predecessor when it is as large as a predecessor. Sidewise requires theta(log n) space for the sequence. The advantage of sidewise is that you don’t need to know n in advance.

(2) There are two common organizations of data in memory to be considered, contiguous arrays and linked lists. Linked lists are more flexible but are less efficient. In particular a linked list requires theta(n) additional storage for links, and algorithms based on linked lists are likely to be computationally less efficient than equivalent algorithms for contiguous arrays.

(3) Algorithms that use O(1) additional space are called in-place algorithms. In place algorithms have the advantage that no additional storage has to be allocated for them.

(3a) Merging runs in contiguous arrays: There are algorithms for merging runs that use O(1) auxilliary space. Unfortunately the best known algorithms aren’t terribly efficient and are difficult to program. If stability is not a criterion, heapsort is faster and is an in-place sort algorithm. The obvious algorithm for merging runs in contiguous arrays requires n/2 additional locations.

(3b) Merging runs in linked lists: There is a simple, obvious algorithm for merging linked lists that requires O(1) space and hence is in-place. The catch is that the links themselve require O(n) additional space. In short, merging is O(1) space for linked lists, but merging of arrays converted to linked list requires O(n) space.

(4) In summary, practical implementations of mergesort require O(n) additional space, either in the form of work space or in the form of links.