Merge Sort for Linked List Criticism in C

Question

I previously implemented a Merge Sort for arrays, so after fixing up my code for the array-based merge sort I have now implemented a merge sort for a basic singly-linked list data structure which only contains the pointer to the data and a pointer to the next "Node". I have tried to use the advice given on the previous post (/q/260010) to help in my endeavor this time around. There are three things I did not change in my current code or my previous code; let me explain my reasoning:

1. (削除) Deceleration (削除ここまで) Declaration and initialization of variables are done separately as I use C90, from habit.
2. I am used to using the <stdint.h> header to write all my code using fixed-width types, so I usually use that for the functions such as merge_sort as for it to stay consistent across platforms. While the user code is written using "int", "short", "char" to emulate a sort of user code feel.
3. I learned to use space for programming instead of tab, and we were told to do 3 spaces, how many space do you recommend 2, 3, 4, or X amount?

Any advice on how to improve my code will help; hopefully this implementation is much better as I have read up online and have been informed that merge sort is usually preferred for linked list and large sets of data.

TLDR - please advise on how to improve my implementation of merge sort for the linked list version. And how many spaces do you use for indentation?

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
struct Node{
 void *data;
 struct Node* next;
};
/*triple ref pointer are really cool as you don't need two pointers*/
int32_t split_list(struct Node *current, struct Node **front, struct Node **middle)
{
 uint32_t length, length_of_middle;
 struct Node *current_temp = current;
 struct Node **triple_ref = &current;
 if(current == NULL)
 {
 *front = *middle = NULL;
 return -1;
 }
 *front = current;
 *middle = current;
 length = length_of_middle = 0;
 while(current_temp != NULL)
 {
 current_temp = current_temp->next;
 length++;
 }
 while(length_of_middle < length / 2)
 {
 triple_ref = &((*triple_ref)->next);
 length_of_middle++;
 }
 *middle = *triple_ref;
 *triple_ref = NULL;
 return 0;
}
int32_t merge_sort(struct Node **head, int compare(const void *, const void *))
{
 struct Node *front, *middle;
 struct Node temp;
 struct Node *current = &temp;
 if(head == NULL)
 {
 return -1;
 }
 else if((*head)->next == NULL)
 {
 return 0;
 }
 split_list(*head, &front, &middle);
 merge_sort(&front, compare);
 merge_sort(&middle, compare);
 while(front != NULL && middle != NULL)
 {
 if(compare(front, middle) <= 0)
 {
 current->next = front;
 front = front->next;
 current = current->next;
 }
 else
 {
 current->next = middle;
 middle = middle->next;
 current = current->next;
 }
 }
 if(front != NULL)
 {
 while(front != NULL)
 {
 current->next = front;
 front = front->next;
 current = current->next;
 }
 }
 else
 {
 while(middle != NULL)
 {
 current->next = middle;
 middle = middle->next;
 current = current->next;
 }
 }
 *head = temp.next;
 return 0;
}
/*user code*/
int compare(const void *ptr1, const void *ptr2)
{
 const struct Node *node1, *node2;
 node1 = ptr1;
 node2 = ptr2;
 return *(int *)(node1->data) - *(int *)(node2->data);
}
void print_list(const struct Node *node)
{
 printf("\n");
 while(node != NULL)
 {
 printf("%d ", *(int *)(node->data));
 node = node->next;
 }
 printf("\n");
}
int32_t push_list(struct Node **head, void *val, const size_t size_of_element)
{
 struct Node *node;
 if(head == NULL)
 {
 return -1;
 }
 node = malloc(sizeof(*node));
 if(node == NULL)
 {
 return -1;
 }
 /*copy data*/
 node->data = malloc(size_of_element);
 if(node->data == NULL)
 {
 free(node);
 return -1;
 }
 memcpy(node->data, val, size_of_element);
 node->next = NULL;
 /*insertion*/
 if(*head != NULL)
 {
 struct Node *current;
 current = *head;
 while(current->next != NULL)
 {
 current = current->next;
 }
 current->next = node;
 return 0;
 }
 *head = node;
 return 0;
}
void free_list(struct Node *head)
{
 struct Node *temp;
 while(head != NULL)
 {
 temp = head;
 head = head->next;
 free(temp->data);
 free(temp);
 }
}
int main(void)
{
 struct Node *head;
 struct Node *front, *middle;
 int i;
 i = 10;
 /* i = 666;*/
 /*add values*/
 head = front = middle = NULL;
 for(; i > -1; i--)
 {
 push_list(&head, &i, sizeof(i));
 }
 i = 10;
 push_list(&head, &i, sizeof(i));
 i = -1;
 push_list(&head, &i, sizeof(i));
 /*print sort print*/
 print_list(head);
 merge_sort(&head, &compare);
 print_list(head);
 free_list(head);
 return 0;
}

Answer 1

I learned to use space for programming instead of tab, and we were told to do 3 spaces, how many space do you recommend 2, 3, 4, or X amount?
And how many space do you use when programming?

This is a style issue and best to follow your group's coding standard which apparently is 3. I use 2.

A good coding environment allows you to change the indent on the entire file quickly with a set-up option and invoking that auto formatter.

If you are manually editing for the correct indentation, you are inefficient. Use an auto-formatter.

---

Deceleration ....

Whoa, slow down there 😉. Did you mean Declaration?

---

Namespace

Rather than

struct Node{
int32_t split_list()
int32_t merge_sort()
void print_list()
int32_t push_list()
void free_list()

Consider a uniform naming

struct DList {
int32_t DList_split()
int32_t DList_merge_sort()
void DList_print()
int32_t DList_push()
void DList_free()

Form a DList.h header file and segregate your DList functions into a DList.c file.

Weak compare

*(int *)(node1->data) - *(int *)(node2->data) risks UB and an incorrect result when the subtraction incurs overflow.

Instead:

int i1 = *(int *)(node1->data);
int i2 = *(int *)(node2->data);
return (i1 > i2) - (i1 < i2);

int vs. int32_t vs ....

I see little value is using int32_t here. Recommend reworking code to size_t for a type that relates to array indexing and int/bool for a simple success flag.

Minor: () not needed

Style issue:

// node = malloc(sizeof(*node));
node = malloc(sizeof *node);

• Toby Speight: Sorry, I fixed the typo in the question, spoiling your pun...
• CLox: Got it. I need to change my functions name for the linked list for it to be more consistent! By the way Nice pun, I do need to slow down.

Answer 2

• No naked loops. Every loop represents an important algorithm, and as such deserves a name. For example, the loops in split_list really are

   uint32_t list_length(struct Node *);
  

  and

   struct Node * advance(struct Node *, uint32_t);
  

• split_list is a bit more complicated than necessary. The fact that front becomes current is known in advance. Do we really need to pass it?

  Similarly, I don't see the reason for triple_ref to be a ** (BTW, the name is really confusing - why triple?).

  All that said, consider

   struct Node * split_list(struct Node * current)
   {
   if (current == NULL) {
   return MULL;
   }
   uint32_t half_length = list_length(current) / 2;
   struct Node * pre_middle = advance(current, half_length);
   struct Node * middle = pre_middle->next;
   pre_middle->next = 0;
   return middle;
   }
  

• I don't see the reason to for merge_sort to return an integer. This value is never tested anyway. It is much more natural to return head:

   struct Node * merge_sort(struct Node * head, int compare(const void *, const void *));
  

• There is no need to loop over the unmerged remains of the lists. They are already good, and we don't care about current any more.

   if (front != NULL) {
   current->next = front;
   } else {
   current->next = middle;
   }
  

• current = current->next is performed in both if and else branches of merging. Lift it out.

• CLox: The reason I use the "triple_ref" as name was because of this video. youtube.com/… by Computerphile. And that is my bad as its more of a concept as compared to an actual triple ref pointer.