Merge sorting a singly-linked list in C - follow-up

Question

(See the initial iteration.)

Continuing from Merge sorting a singly-linked list in C, I have incorporated the points made by @vnp.

Now it looks like this:

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct linked_list_node {
 int value;
 struct linked_list_node* next;
} linked_list_node;
/*******************************************************************************
* This fuction converts the command line arguments to a linked list. *
*******************************************************************************/
static linked_list_node* build_linked_list_from_args(int argc, const char* argv[])
{
 if (argc <= 1)
 {
 return NULL;
 }
 linked_list_node* list = calloc(argc - 1, sizeof(*list));
 for (size_t node_index = 0; node_index < argc - 1; ++node_index)
 {
 list[node_index].value = atoi(argv[1 + node_index]);
 list[node_index].next = node_index == argc - 2 ?
 NULL :
 &list[node_index + 1];
 }
 return list;
}
/*******************************************************************************
* This function prints the entire linked list to stdout. *
*******************************************************************************/
static void print(linked_list_node* head)
{
 printf("[");
 linked_list_node* current_node = head;
 if (current_node)
 {
 printf("%d", current_node->value);
 current_node = current_node->next;
 }
 while (current_node)
 {
 printf(" %d", current_node->value);
 current_node = current_node->next;
 }
 printf("]");
}
/*******************************************************************************
* This function merges stabily the two input lists that are expected to be *
* sorted. *
*******************************************************************************/
static linked_list_node* merge(linked_list_node* left_head,
 linked_list_node* right_head)
{
 linked_list_node* merged_list_head;
 linked_list_node* merged_list_tail;
 if (right_head->value < left_head->value)
 {
 merged_list_head = right_head;
 merged_list_tail = right_head;
 right_head = right_head->next;
 }
 else
 {
 merged_list_head = left_head;
 merged_list_tail = left_head;
 left_head = left_head->next;
 }
 while (left_head && right_head)
 {
 if (right_head->value < left_head->value)
 {
 merged_list_tail->next = right_head;
 merged_list_tail = right_head;
 right_head = right_head->next;
 }
 else
 {
 merged_list_tail->next = left_head;
 merged_list_tail = left_head;
 left_head = left_head->next;
 }
 }
 merged_list_tail->next = left_head ? left_head : right_head;
 return merged_list_head;
}
/*******************************************************************************
* This function splits the input linked list in two sublists and returns the *
* head of the right one. *
*******************************************************************************/
static linked_list_node* split(linked_list_node* head)
{
 linked_list_node* slow = head;
 linked_list_node* fast = head;
 linked_list_node* prev_slow = NULL;
 while (fast && fast->next)
 {
 prev_slow = slow;
 slow = slow->next;
 fast = fast->next->next;
 }
 linked_list_node* right_sublist_head = prev_slow->next;
 prev_slow->next = NULL;
 return right_sublist_head;
}
/*******************************************************************************
* This function implements the actual sorting routine. *
*******************************************************************************/
static linked_list_node* sort_impl(linked_list_node* head)
{
 if (!head->next)
 {
 return head;
 }
 linked_list_node* right_sublist_head = split(head);
 return merge(sort_impl(head), sort_impl(right_sublist_head));
}
/*******************************************************************************
* This function sorts the input linked list whose the first node is 'head'. *
*******************************************************************************/
linked_list_node* sort(linked_list_node* head)
{
 if (!head || !head->next)
 {
 return head;
 }
 return sort_impl(head);
}
int main(int argc, const char * argv[]) {
 linked_list_node* head = build_linked_list_from_args(argc, argv);
 print(head);
 puts("");
 head = sort(head);
 print(head);
 puts("");
 return 0;
}

As always, any critique is much appreciated.

Answer 1

1. Utilize const to indicate the referenced data is not changed and allow optimizations.

   // static void print(linked_list_node* head)
   static void print(const linked_list_node* head)
   

2. In print(), code repeated all for the sake of a " ". Suggested simplification:

   const char *sep = "";
   while (current_node) {
    printf("%s%d", sep, current_node->value);
    sep = " ";
    current_node = current_node->next;
   }
   

3. I'd expect non-static function names tailored to linked lists. Example: sort() is too likely to collide with other code.

   // linked_list_node* sort(linked_list_node* head)
   linked_list_node* linked_list_sort(linked_list_node* head)
   

4. Many functions are static. None of these should be in the same .c file as main(). Better to have all linked list functions in a file like linked_list.c with a corresponding linked_list.h header file.

5. Expect more that just sort() to not be static. Certainly build_linked_list_from_args() is meant to be visible.

6. Consider a call like merge(list1, list1). Will code work? If that functionality is not needed, use restrict to indicate that and allow more optimizations.

   // linked_list_node* merge(linked_list_node* left_head, linked_list_node* right_head)
   linked_list_node* merge(linked_list_node* restrict left_head, 
    linked_list_node* restrict right_head)
   

Minor

1. Spelling fuction --> function.

2. sizeof(*list) can be coded simpler as sizeof *list. (style issue)

3. Not a fan of using printf(string) to print strings. printf() expects that first argument to point to a string used as a format - which is a problem should it contain "%". Consider fputs(string, stdout)

4. Uncertain that const is generally OK in main(). Since it is test code, suggest simplifying.

   // int main(int argc, const char * argv[])
   int main(int argc, char * argv[])
   

5. Add date and your ID (name) to the file as a comment.

6. Format: The below format is hard to maintain with automatic formatting tools (at least mine). Maybe it does well with yours. Formatting is a pain and should not be maintained manually. Assuming you did not use such a tool, try one.

   static linked_list_node* merge(linked_list_node* left_head,
    linked_list_node* right_head)
   

[Edit]

Simplified merge(), only while() loop needed.
Down-side: need a linked_list_node variable and not just a linked_list_node *.

static linked_list_node *merge(linked_list_node *left, linked_list_node *right) {
 linked_list_node head; // Only use next field
 linked_list_node *tail = &head;
 while (left && right) {
 if (right->value < left->value) {
 tail->next = right;
 tail = right;
 right = right->next;
 } else {
 tail->next = left;
 tail = left;
 left = left->next;
 }
 }
 tail->next = left ? left : right;
 return head.next;
}

Answer 2

Readability regarding docstrings:

You've written docstrings to describe your functions as following: "This function [describes what the function does]".

/*******************************************************************************
* This function splits the input linked list in two sublists and returns the *
* head of the right one. *
*******************************************************************************/
static linked_list_node* split(linked_list_node* head)
/*******************************************************************************
* This function sorts the input linked list whose the first node is 'head'. *
*******************************************************************************/
linked_list_node* sort(linked_list_node* head)

Beginning every docstring with "This function" is redundant and hurts readability. Any potential reader knows that the subject of the comment is a function. Instead:

/*******************************************************************************
* Splits the input linked list in two sublists and returns the
* head of the right one. *
*******************************************************************************/
static linked_list_node* split(linked_list_node* head)
/*******************************************************************************
* Sorts the input linked list whose the first node is 'head'.
*******************************************************************************/
linked_list_node* sort(linked_list_node* head)

It may seem petty but if the reader was scanning between a large number of docstrings, it makes a significant difference in how quickly and easily distinguishable they are.

Answer 3

If performance is one of the goals for a linked list sort, then a bottom up merge sort using a small (26 to 32) array of pointers to nodes is a much faster method, than using an array oriented top down approach which requires repeated scanning of sub-lists (to emulate random access iterators) in order to split them in half.

Wiki psuedo code:

http://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists

I can add example C code if interested.