Bottom up merge sort on Linked List

Question

Bottom up merge sort treats a list each element of size 1, and iteratively merge the sub-lists back and forth until they are in sorted order. This makes it very attractive to use bottom up merge sort to sort linked list as they are already "separated".

I'm trying to implement bottom up merge sort in C language, and realised that there are various approach to implement bottom up merge sort; in particular, I'm using this approach:

1. Insert single lists into a queue
2. Dequeue first two lists and merge them
3. Enqueue merged lists (merged items go to the end)
4. Repeat step 1-3 until they are in sorted order

However, I'm struggling to implement the following:

• Merge linked-lists without using extra O(n) space (if possible)

Hence, my questions are:

• How would one implement this correctly in C language? (in particular: the handling of repeating the dequeue and enqueue process until it's fully sorted) How would one know if the entire queue is in sorted order? I'm thinking of keeping track of the *head pointer(s) in a list.
• Is merge sort stable in this case? Why?
• The running time of bottom-up merge sort is still O(nlogn). However, does this bottom up merge sort use O(n) space? Suppose the linked-list we implement is already a queue.
• Extra question: is there a better alternative to implement bottom-up merge sort on linked list?

I suppose this is one of the advantage of using bottom-up merge sort on linked list, as it is more space efficient than using bottom-up merge sort on arrays. Correct me if I'm wrong.

Answer 1

There's a clever method that uses a fixed size array (26 or 32 are common sizes) array of pointers to nodes, some working local pointers to nodes, and a standard mergelists() function that merges two already sorted lists, and needs to handle empty lists to make the main code simpler. Nodes are merged into the array, then the array is merged into a single sorted list. The first part of this logic is:

    // initialize array[] to all NULLs
    while(plist != NULL){
        pmerge = plist;
        plist = plist->next;
        pmerge->next = NULL;
        for(i = 0; i < array size; i++){
            if(array[i] == NULL)
                break;
            pmerge = mergelists(array[i], pmerge);
            array[i] = NULL;
        }
        if(i == array size)i--;
        array[i] = pmerge;
    }

The size of the list doubles as i increases, array[i] is either NULL or points to a list with 2 to the power i nodes.

Then the array is merged into a single list, again with just a loop and a call to mergelists(). See if you can figure out this part.

Answer 2

1. How would one implement that? is a bit too broad question, I'm afraid.
2. Mergesort is stable provided that when you encounter equal items in two sublists, you take them from the 'left' (earlier) sublist first.
3. With a linked list you can use O(1) space; just unlink sublist sequentially, and append them to a new temporary list after merging, then use the new list in the next iteration with longer sublists. You will only need to keep additional 'head' and 'tail' pointers for a temporary list.
4. Yes, there is: unlink longest possible increasing runs instead of 1, 2, 4... items sublists. That is as good as the original algorithm in the worst case (input in reverse order makes one-item runs in the first iteration), but it makes a full use of an existing partial order if there is one (for a fully sorted input it just scans the list once).