Which sorting algorithm is best for sorting a single list

Question

I read in-place sorting algorithm for sorting linked lists. According to Wikipedia

Merge sorting 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) additional space, and a slow random access performance of the linked list makes some other algorithms (e.g. quicksort ) are idle, while others (for example, heapsort) are completely impossible.

As far as I know, the merge sorting algorithm is not an in-place sorting algorithm and has the worst spatial complexity of the O(n) auxiliary. Now, with this in mind, I can’t decide if there is a suitable algorithm for sorting a separately linked list with O(1) auxiliary space.

Answer 1

As Fabio A. noted in a comment, the sorting algorithm implied by the following merge and split implementations actually requires O (log n) extra space in the form of stack frames to control recursion (or their explicit equivalent). The O (1) -space algorithm is possible using a completely different upward approach.

Here we use the O (1) -space merge algorithm, which simply creates a new list by moving the bottom 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; } 

You can avoid pointer to pointer p special casing of the first element to be added to the output list, but I think the way I did this is clearer.

Here is an algorithm for dividing an O (1) space, which simply splits the list into two parts of equal size:

 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; } 

Note that half moves only half as much as in . When this function returns, the list originally accepted as in will be changed so that it contains only the first ceil elements (n / 2), and the return value is a list containing the remaining elements (n / 2).

Answer 2

This somehow reminds me of my answer to the question of the Dutch national flag .

After I thought that this is what I came to, let's see if this works out. I suppose the main problem is the merge phase of the merge in O(1) extra-space.

Our view of the linked list:

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

As a result, you will complete this merge step:

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

Be p and q pointers for the segments we want to combine.

Just add your nodes after the tail pointer. If *p <= *q you add p to 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 end of our q list becomes complicated)

Now, if you move them, you will quickly lose information about where you are. You can beat this with a smart way to move pointers or add lengths to the equation. I definitely prefer the latter. The approach becomes as follows:

 [ 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 can use the extra O(1) space to move your elements.