• 1

• 31.8k
• 15
• 77
• 202

• 31.8k
• 15
• 77
• 202

I have this C implementation of the merge sort for sorting singly-linked lists:

#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* head = malloc(sizeof(*head));
 linked_list_node* tail = head;
 head->value = atoi(argv[1]);
 for (size_t arg_index = 2; arg_index < argc; ++arg_index)
 {
 linked_list_node* new_node = malloc(sizeof(*new_node));
 new_node->value = atoi(argv[arg_index]);
 tail->next = new_node;
 tail = new_node;
 }
 tail->next = NULL;
 return head;
}
/*******************************************************************************
* 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("]");
}
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 implements the actual sorting routine. *
*******************************************************************************/
static linked_list_node* sort_impl(linked_list_node* head)
{
 if (!head->next)
 {
 return head;
 }
 linked_list_node* left_sublist_head = head;
 linked_list_node* right_sublist_head = head->next;
 linked_list_node* left_sublist_tail = left_sublist_head;
 linked_list_node* right_sublist_tail = right_sublist_head;
 linked_list_node* current_node = right_sublist_tail->next;
 bool left = true;
 // Split the input linked list into two sublist of almost the same length:
 while (current_node)
 {
 if (left)
 {
 left_sublist_tail->next = current_node;
 left_sublist_tail = current_node;
 left = false;
 }
 else
 {
 right_sublist_tail->next = current_node;
 right_sublist_tail = current_node;
 left = true;
 }
 current_node = current_node->next;
 }
 left_sublist_tail ->next = NULL;
 right_sublist_tail->next = NULL;
 return merge(sort_impl(left_sublist_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;
}

So, how am I doing here? Is there anything I could improve?