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);

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.