I'm trying to write a recursive merge sort on a linked list. I'm basically stuck on the split portion of it currently. I came up with a solution quite similar to many other solutions I've found on the web. Many people say it works but so far my solution doesn't seem to. Here is my split code:
LLN* LLN::split() {
if(next == NULL) return NULL;
LLN* ret = this->next;
this->next = ret->next;
ret->next = ret->next->split();
return ret;
}
Now, here is my problem. This does seem to split the list, but the list I wish to return just gets lost for some reason. For example, the following data is inserted into the list...
a
b
c
d
e
f
g
When printed each list, I should have the output for one list be...
g
e
c
a
The other should be
f
d
b
The ret list should be the "f d b" one. However, when from that code snippet, I return "ret" or "this" they both give the output "g e c a." I've tried to retrieve the f d b list but it seems to be lost. I've drawn this algorithm out on paper a hundred times and I can't figure it out what is wrong. Any ideas about this?
Unsolved 
