What is the best in place sorting algorithm to sort a singly linked list

Question

I've been reading on in place sorting algorithm to sort linked lists. As per Wikipedia

Merge sort is often the best choice for sorting a linked list: in this situation it is relatively easy to implement a merge sort in such a way that it requires only Θ(1) extra space, and the slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.

To my knowledge, the merge sort algorithm is not an in place sorting algorithm, and has a worst case space complexity of O(n) auxiliary. Now, with this taken into consideration, I am unable to decide if there exists a suitable algorithm to sort a singly linked list with O(1) auxiliary space.

Answer 1

As pointed out by Fabio A. in a comment, the sorting algorithm implied by the following implementations of merge and split in fact requires O(log n) extra space in the form of stack frames to manage the recursion (or their explicit equivalent). An O(1)-space algorithm is possible using a quite different bottom-up approach.

Here's an O(1)-space merge algorithm that simply builds up a new list by moving the lower item from the top of each list to the end of the new list:

struct node {
    WHATEVER_TYPE val;
    struct node* next;
};

node* merge(node* a, node* b) {
    node* out;
    node** p = &out;    // Address of the next pointer that needs to be changed

    while (a && b) {
        if (a->val < b->val) {
            *p = a;
            a = a->next;
        } else {
            *p = b;
            b = b->next;
        }

        // Next loop iter should write to final "next" pointer
        p = &(*p)->next;
    }

    // At least one of the input lists has run out.
    if (a) {
        *p = a;
    } else {
        *p = b;        // Works even if b is NULL
    }

    return out;
}

It's possible to avoid the pointer-to-pointer p by special-casing the first item to be added to the output list, but I think the way I've done it is clearer.

Here is an O(1)-space split algorithm that simply breaks a list into 2 equal-sized pieces:

node* split(node* in) {
    if (!in) return NULL;    // Have to special-case a zero-length list

    node* half = in;         // Invariant: half != NULL
    while (in) {
        in = in->next;
        if (!in) break;
        half = half->next;
        in = in->next;
    }

    node* rest = half->next;
    half->next = NULL;
    return rest;
}

Notice that half is only moved forward half as many times as in is. Upon this function's return, the list originally passed as in will have been changed so that it contains just the first ceil(n/2) items, and the return value is the list containing the remaining floor(n/2) items.

Answer 2

This somehow kind of remind me about my answer to a Dutch National Flag Problem question.

After giving it some thought this is what I came up to, let's see if this works out. I suppose the main problem is the merging step of the mergesort in O(1) extra-space.

Our representation of a linked-list:

[ 1 ] => [ 3 ] => [ 2 ] => [ 4 ]
  ^head                      ^tail

You end up with this merging step:

[ 1 ] => [ 3 ] => [ 2 ] => [ 4 ]
  ^p                ^q       ^tail

Being p and q the pointers for the segments we want to merge.

Simply add your nodes after the tail pointer. If *p <= *q you add p at the tail.

[ 1 ] => [ 3 ] => [ 2 ] => [ 4 ] => [ 1 ]
  ^p       ^pp      ^q/qq    ^tail    ^tt

Otherwise, add q.

[ 1 ] => [ 3 ] => [ 2 ] => [ 4 ] => [ 1 ] => [ 2 ]
  ^p       ^pp      ^q       ^qq/tail          ^tt

(Keeping track of the ending of our list q becomes tricky)

Now, if you move them you will rapidly lose track of where you are. You can beat this having a clever way to move your pointers or add the lengths into the equation. I definitely prefer the latter. The approach becomes:

[ 1 ] => [ 3 ] => [ 2 ] => [ 4 ]
  ^p(2)             ^q(2)    ^tail

[ 3 ] => [ 2 ] => [ 4 ] => [ 1 ]
  ^p(1)    ^q(2)             ^tail

[ 3 ] => [ 4 ] => [ 1 ] => [ 2 ]
  ^p(1)    ^q(1)             ^tail

[ 4 ] => [ 1 ] => [ 2 ] => [ 3 ]
  ^p(0)/q(1)                 ^tail

[ 1 ] => [ 2 ] => [ 3 ] => [ 4 ]
  ^q(0)                      ^tail

Now, you use that O(1) extra-space to be able to move your elements.