The structure of your sort is off: sort() and merge() should be mutually recursive:
split xs into lefts, rights
if (length of lefts > 1) sort(lefts)
if (length of rights > 1) sort(rights)
for (left:lefts, right:rights)
This is very simplified pseudocode, You'll have to think hardest about how to handle that merge loop.
An important consideration is the way you manage the list. Right now you are iterating over every element of the list to move it (or worse, copy it) to another list. Don't do that; Just cut and paste nodes.
For example, code that splits the list should look something like this:
int N, n, temp;
element_t* node = list->head;
N = list_length( list );
// Don't sort an unsortable list
if (N < 2) return;
// just swap the two elements if necessary
if (N == 2)
if (list->head->val > list->tail->val)
temp = list->head->val;
list->head->val = list->tail->val;
list->tail->val = temp;
// Now for the real work
n = N / 2;
// node <-- node PRIOR to the last n or n-1 elements
while (n--) node = node->next;
// Split the list.
list_t* left = list_create();
list_t* right = list_create();
// splice out the right side
right->head = node->next;
right->tail = list->tail;
right->length = N - n; // (see below)
// splice out the left side
left->head = list->head;
left->tail = node;
left->length = n; // (see below)
// finish breaking all the connections from the old list
node->next = NULL;
list->head = list->tail = NULL;
list->length = 0; // (see below)
// Now you can merge, making sure to place the result in some good place.
// I recommend a third argument to merge() for the result:
merge( left, right, list );
// At this point, left and right should again be empty lists, because all their nodes
// were moved into 'list'.
left = list_destroy( left );
right = list_destroy( right );
The length function could also be reduced to O(1) complexity. Since you are taking the time to track head and tail of your list, there is no reason why you can't track its length also.
int list_length( list_t* list )
return list ? list->length : 0;
(I do understand that you might not have the ability to modify the list structure, though. If you can't then just get rid of lines 34, 39, and 44.)
A quick primer on complexity.
The point of a merge sort is to do things efficiently, which in the case of sorting, means touching each element of the list as few times as possible. That is why you should:
1. not copy elements one-by-one from the old to temporary lists.
2. avoid a length function that has to count elements.
The only counting complexity you should have to put up with is simply finding the middle element in the list. Beware fencepost errors.
Finally, a technical detail. POSIX reserves names ending in "_t", meaning that the "list_t" and "element_t" are in potential conflict with stuff in the OS API, which is bad.
Hope this helps.