Nick <(E-Mail Removed)> writes:

> To help me follow this point, could you re-write this without the

> recursion -

> http://groups.google.com/group/comp....c56651e3?hl=en
This is Chris Torek's recursive linked-list mergesort.

> It's not obvious to me how to do it while keeping it simple and

> elegant.
Chris's algorithm is a `top-down' mergesort. It's not especially easy

to make such a beast nonrecursive without an explicit stack. But

there's a very close cousin, a `bottom-up' mergesort, which is easy to

make nonrecursive.

The difference is as follows.

* A top-down mergesort splits its input into two sublists of similar

length, recursively sorts the two halves, and merges them together.

So if you start with N items, then you split them into two lists of

N/2 items at the top level, four lists of N/4 items at the next, and

so on until you have only trivial sublists.

* A bottom-up mergesort builds up islands of sortedness. It starts by

cutting the input into pairs of sublists of (say) length 1 which are

obviously sorted, merging the pairs, and concatenating the merged

results. Then every pair of items is sorted; so we cut the list

into pairs of lists of length 2, merging and concatenating.

This latter is quite easy to implement nonrecursively: all you need to

remember is how long the sublists you're meant to work with are. I

think the resulting code is fairly elegant, but I'll let you be the

final judge. Note the triple indirection in `mergelists': I think this

is one of the more obvious natural applications for a triply-indirected

pointer.

/* Merge together two sorted lists A and B into a single sorted list.

* The sort order is determined by the CMP function; if CMP decides that two

* elements are equivalent then prefer the element from list A. On exit,

* **TAILP is set to point to the start of the merged list, and *TAILP is the

* address of the `next' link of the last node of the merged list, so that

* further stuff can be appended later: several merged lists can be

* accumulated simply by passing the same TAILP argument repeatedly to

* `mergelists'; to terminate the list finally, set **TAILP = 0.

*/

static void mergelists(struct list ***tailp,

struct list *a, struct list *b,

int (*cmp)(const struct list *,

const struct list *))

{

struct list **tail = *tailp;

/* Choose the lesser item from the two list heads and advance. Continue

* until we run out of one of the lists; when done; set A to the (possibly)

* nonempty list.

*/

for (;

{

if (!b) break;

else if (!a) { a = b; break; }

else if (cmp(a, b) <= 0) { *tail = a; tail = &a->next; a = a->next; }

else { *tail = b; tail = &b->next; b = b->next; }

}

/* Append the (possibly) nonempty list onto the accumulated output, and

* find the end of it.

*/

*tail = a;

if (a) {

while (a->next) a = a->next;

tail = &a->next;

}

/* Tell the caller where the end of the list is. */

*tailp = tail;

}

/* Sort a list L using in-place list mergesort.

* The CMP function is a preorder, outputting <0, 0, or >0 according to

* whether the payload of its left argument is less than, equivalent to, or

* greater than, its right argument; `equivalence' must indeed be an

* equivalence relation, and CMP must be transitive. The sort is stable: two

* nodes with equivalent payloads remain in the same relative order.

*/

static struct list *mergesort(struct list *l,

int (*cmp)(const struct list *,

const struct list *))

{

size_t i, n = 1;

struct list *head, **tail;

struct list *a, *b, **p;

int done = 0;

/* An empty input is a nasty edge case. Dispose of it in advance. */

if (!l) return (0);

/* Main loop. We cut the list into pairs of sublists of length N, and

* merge each pair together, concatenating the results to form a new list

* in which each consecutive run of 2 N elements is sorted. Then we double

* N. When N is longer than the list, we're done.

*/

do {

/* Collect the merged sublist pairs. */

tail = &head;

/* While there is more input list to consume, cut out two sublists of

* length N.

*/

while (l) {

/* Find the start and end of the first sublist. Note that the extra

* level of indiration in P allows it to lag one node behind, so that

* we can terminate the sublist when we've counted enough.

*/

p = &l; a = *p;

for (i = n; i && *p; i--) p = &(*p)->next;

/* Find the start and end of the second sublist. */

b = *p; *p = 0; p = &b;

for (i = n; i && *p; i--) p = &(*p)->next;

l = *p; *p = 0;

/* If we've hit the end of the input, and haven't produced any output,

* then our two sublists must contain all of the elements. Therefore,

* when we've merged them, we'll have sorted the entire input, and

* we'll be finished.

*/

if (!l && tail == &head) done = 1;

/* Merge the sublists, and append to our output. The A list consists

* of elements earlier than the B list, and `mergelists' will preserve

* the relative order of equivalent nodes, so the sort is stable.

*/

mergelists(&tail, a, b, cmp);

}

/* Terminate the output list, and make it be the new input. */

*tail = 0;

l = head;

n <<= 1;

} while (!done);

/* Finished. */

return (l);

}

-- [mdw]