Segmentation Fault in Mergesort implementation

Question

I have a program Mergesort which works with an unordered linked list.The problem I get is Segmentation Fault (core dumped).

Actually I get this error quite frequently but I do not know how to fix it. Moreover, it does not show any error or warning messages to find it. In this source code and in other case in general, I really need to know why I have this and how I fix it.

#include <stdio.h>
#include <stdlib.h>

typedef struct node_t node;
typedef struct node_t { int key; node *next; } node;
static node *head, *z;
node *merge(node *a, node *b)
{
    z->next =z;
    node *c = z;
    do
    {
        if (a->key > b->key)
        {
            c->next = a; c = a; a = a->next;
        }
        else
        {
            c->next = b; c = b; b = b->next;
        }
    } while (c != z);
    c = z->next;
    z->next = NULL;
    return c;
}
node *mergesort(node *c) {
    node *a = NULL; 
    node *b = NULL;
    if (c != NULL && c->next->next != NULL) {
        a = c; b = c;
        while (b->next != NULL && b->next->next != NULL) {
            c = c->next;
            b = b->next->next;
        }
        b = c->next;
        c->next = NULL;
        return merge(mergesort(a), mergesort(b));
    }
    return c;
}
void printList(node* node) 
{ 
    while (node != NULL) { 
        printf("%d ", node->key); 
        node = node->next; 
    } 
} 
node *listcreate(int n, node *a)
{
    node *head = NULL;
    node *temp = NULL;
    node *p = NULL;
    int i=0;
    while(i<n)
    {
        temp = (node*) malloc(sizeof(node*));
        printf("Please insert the number: ");
        scanf("%d", &(temp->key));
        temp->next = NULL;
        if(head == NULL)
        head = temp;
        else
        {
            p = head;
            while(p->next != NULL)
            p = p->next;
            p->next = temp;
        }
        i++;
    }
    a = head;
}
int main() 
{ 
    node *a = NULL;
    listcreate(3, a);
    a = mergesort(a);
    printf("Sorted Linked List is: \n"); 
    printList(a); 

    getchar(); 
    return 0; 
}

*"it does not show any error or warning messages"* - Yes, it does. Compile with `-Wall -Wextra`. Furthermore, what's the purpose of `z`? That makes no sense. — klutt, Feb 10 '20 at 09:09
z is the sentinel key, you can search it on Google. Do you think it is the cause of this error? — Hoang Nam, Feb 10 '20 at 09:10
@HoangNam Most certainly, yes. If that's your sentinel, then you may want to initialize it to something other than `NULL`. — dragosht, Feb 10 '20 at 09:13
If `z` is NULL, then `c = z->next;` will cause an error, yes. — klutt, Feb 10 '20 at 09:31
@klutt I think ``z = NULL`` means that ``z->next = z`` so it can't cause any errors. If you're right, how do you fix that? — Hoang Nam, Feb 10 '20 at 09:37
@HoangNam But then if `z` is your sentinel node, what would you use `z->next` for? — dragosht, Feb 10 '20 at 09:41
`z` is not a "sentinel". It's not a node at all; it's a null pointer. Your code would be the same if you replaced every usage of `z` with `(node*)NULL`. Once you do that, it will be clearer to you why your code is incorrect. — Sneftel, Feb 10 '20 at 09:45
I think the OP's logic here is to have a circular linked list by creating a loop around the sentinel node. Kind of like this: https://www.quora.com/What-is-the-sentinel-node-in-a-circular-linked-list . But the list initialization lacks all the steps required to do so. @HoangNam , am I getting this right? — dragosht, Feb 10 '20 at 09:48

Serge Ballesta · Accepted Answer · 2020-02-10T13:03:53.260

0

First of all calling your function mergesort while including stdlib.h is incorrect and should raise an error with recent C compilers.

Next, this sequence of code invokes Undefined Behaviour by dereferencing a null pointer:

node *z = NULL;
node *c = z;
c->next = a;  //  UB!

At that point, c is NULL, so you shall not use c->next. Doing it with common C implementation tries to write into disallowed memory causing the seg fault.

Your algorythm tries to use a sentinel, but IMHO it is not a appropriate use case. It is simpler to just remember the first value. And you should also handle the case where you reach the end of one of both sorted list. The code could become:

node *merge(node *a, node *b)
{
    node *c = z;           // current node initialized to null
    node *top;             // declare the future return value
    do
    {
        if (a->key > b->key)
        {
            if (c == z) top = a;    // if first value, remember it
            else c->next = a;       // else add the node to current list
            c = a; a = a->next;
            if (a == NULL) {        // explicitely handle end of input list
                c->next = b;
                break;
            }
        }
        else
        {
            if (c == z) top = b;
            else c->next = b; 
            c = b; b = b->next;
            if (b == NULL) {
                c->next = a;
            break;
            }
        }
    } while (c != z);
    return top;
}

But that is not all. Your code is a mix of C and C++. You only use C library functions but compile the code with a C++ compiler. C language does not allow function overloads, so you should not re-use the name of a function of the standard library with a different parameter set (mergesort). And in C language, you need not cast malloc.

Even with my fix, your code will break on any decent C compiler if you do not change the name of the mergesort function. You have been warned.

edited Feb 10 '20 at 13:03

answered Feb 10 '20 at 10:52

Serge Ballesta

143,923
11
122
252

Actually I still don't know why "mergesort while including stdlib.h" is wrong. stdlib here provides me the malloc function – Hoang Nam Feb 10 '20 at 10:55
`stdlib.h` does provide the declaration of `malloc`. Unfortunately it also declares `int mergesort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));` which conflicts with your one. – Serge Ballesta Feb 10 '20 at 10:58
I do not provide the parameters that you mention. I provide a different version – Hoang Nam Feb 10 '20 at 10:59
@HoangNam: You may not listen to what we say, but in that case asking question is just useless. I precisely said that the version from stdlib.h **conflicts** with yours (meaning declares different parameters than yours). It would be correct in C++ because of *name mangling* which allows a function to be declared with different parameter sets but is forbidden in C language. – Serge Ballesta Feb 10 '20 at 11:00
ok I'm sorry because I'm newbie to C language, I do not know that there exists ``mergesort`` in the stdlib.h. But i think it's not a big deal because even in that lib, I am able to redefine the function by myself without any errors – Hoang Nam Feb 10 '20 at 11:05
There is a problem in your code. You call ``top`` at the top of your code but then you do nothing with it except for return it at the end of ``merge`` function. You said that it is "declare the future return value" but I don't understand – Hoang Nam Feb 10 '20 at 16:04
@HoangNam: If I read correctly, `top` if set to the first element of one of the sorted sub-lists, and the greater one. I even added a comment saying *if first value, remember it*. I think it is time to learn how to step a code through a debugger. – Serge Ballesta Feb 10 '20 at 16:08

score -2 · Answer 2 · answered Feb 10 '20 at 10:20

For the last question, I think the main reason for segmentation fault is accessing memory that is either not initialized, out of bounds for your program or trying to modify string literals. These may cause a segmentation fault though it is not guaranteed that they will cause a segmentation fault. Here are some of the common reasons for segmentation faults −

Accessing an array out of bounds

Dereferencing NULL pointers

Dereferencing freed memory

Dereferencing uninitialized pointers

Incorrect use of the "&" (address of) and "*" (dereferencing) operators

Improper formatting specifiers in printf and scanf statements

Stack overflow

Writing to read-only memory

Segmentation Fault in Mergesort implementation

2 Answers2