This is a continuation from this thread about a program that used an insertion sort to sort a list:

how-to-sort-datas-linked-list-...htm

The original poster asked for ways to improve this and I mentioned merge sort, and then a discussion evolved about merge sorts. The original poster wasn't responding, so I created this thread with a more descriptive title to continue the discussion.

The stack contains the tree. For a typical top down merge sort, a depth first (left first) tree is dynamically created and followed during recursions and returns from the main sort function. The initial recursion follows the left fork of the tree to split lists until list size is reduced to 1, at which point the first merge operation takes place. Then the tree is traversed up (merge operations) and down (split operations) until the entire tree is traversed.

For a list sort, the tree contains head pointers to list. For arrays, the tree contains indexes or pointers into an array.

Bottom up merge does not use O(n) memory space. For a bottom up merge sort on lists, a fixed size array of head pointers to lists can be used, regardless of n. The microsoft STL bottom up list merge sort implementation uses an fixed size array of 23 pointers, plus 2 temp pointers for merge operations. In my example program (link below) I use an array of 32 pointers.

A basic bottom up merge sort for a list just needs 4 pointers and a few counters to implement a merge sort similar to a tape based merge sort.

On a side note, a natural merge sort is stable if run counts are used instead of relying on compare to determine the boundaries between runs.

Link to an example program of a bottom up merge sort for a list using an array of 32 list pointers.

http://rcgldr.net/misc/sortl.zip

The program currently uses a static array, but this could be changed to a local array and the array reference passed between the two functions that use the array. The program sorts 4,194,304 nodes with psuedo random 64 bit unsigned integers for data. The data is written to a file in order to verify the sorted result (by comparing with known good output).

The program merges nodes one at a time into the lists pointed to by the array. For i = 0 to 30, array[i] points to a list of size 2^i (or else it's NULL). array[31] list size is not limited. After the initial list is merged into the array, the array lists are merged to create a single sorted list. The microsoft STL implemenation for list sort uses the same method (but I got the idea for this from a summation class function I wrote).

- - -

As I posted in that other thread, all that is accomplished during the recursive phase of a top down merge sort is recursively splitting of lists until lists of size 1 are produced, and only then does any actual merging take place.

The key concept of a merge sort is to repeatedly combine sorted lists by merging them together until a single list is produced, and this is the same for both top down or bottom up.

If I'm trying to explain bottom up merge sort using 8 numbered cards, the initial state is 8 groups of 1 card each, and the 8 groups of size 1 are merged in pairs to create 4 groups of size 2, which are then merged to form 2 groups of size 4, which are then merged to create 1 group of size 8.

If I explain the top down approach, I have to start with 1 group of 8 cards, split it to create 2 groups of 4 cards, split those to create 4 groups of 2 cards, and split those to create 8 groups of 1 card, just to get to the bottom up method's initial state.

In my opinion, the main purpose of top down merge sort is as a learning tool used to teach recursion, similar to implementing factorial or fibonacci via recursion. It's not efficient, but it's useful for teaching recursion.