This is a continuation from this thread about a program that used an insertion sort to sort a list:
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.
For a list sort, the tree contains head pointers to list. For arrays, the tree contains indexes or pointers into an array.
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.
Link to an example program of a bottom up merge sort for a list using an array of 32 list pointers.
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 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.