Segmentation fault in my code SLL Natural Merge Sort in C++

Question

This is my code SLL Natural Merge Sort in C++:

#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
    int data;
    Node* link;
}NODE;
typedef struct List{
    NODE* first;
    NODE* last;
}LIST;
void Init(LIST &l){
    l.first = l.last = NULL;
}
NODE* GetNode(int x){
    NODE* p;
    p = (NODE*)malloc(sizeof(NODE));
    if (p==NULL){
        printf("Khong du bo nho!"); return NULL;
    }
    p->data = x;
    p->link = NULL;
    return p;
}

void AddLast(LIST &l, NODE* new_ele){
    if (l.first==NULL){
        l.first = new_ele;
        l.last = l.first;
    }
    else {
        l.last->link = new_ele;
        l.last = new_ele;
    }
}
NODE* InsertLast(LIST &l, int x){
    NODE* new_ele = GetNode(x);    
    if (new_ele == NULL){
        return NULL;
    }
    AddLast(l,new_ele);
    return new_ele;
}
void AddNumber(LIST &l, int a[], int n){
    NODE *p;
    for (int i=0; i<n; i++){
        InsertLast(l,a[i]);
    }
}
void ShowNumber(LIST l){
    NODE* p = l.first;
    printf("Day so: ");
    while (p!=NULL){
        printf("%d ",p->data);
        p = p->link;
    }
    printf("\n");
}
void DistributeList(LIST &l, LIST &l1, LIST &l2){
    NODE *p;
    do{
        p = l.first;
        l.first = p->link; p->link = NULL;

        AddLast(l1,p);
    }while((l.first)&&(p->data<=l.first->data));
    if (l.first)
        DistributeList(l,l2,l1);
    else
        l.last = NULL;
}
void MergeList(LIST &l, LIST &l1, LIST &l2){
    NODE* p;
    while ((l1.first)&&(l2.first)){
        if (l1.first->data<=l2.first->data){
            p = l1.first;
            l1.first = p->link;
        }
        else{
            p = l2.first;
            l2.first = p->link;
        }
        p->link = NULL;
        AddLast(l,p);
    };
    if (l1.first){
        l.last->link = l1.first;
        l.last = l1.last;
    }
    else if (l2.first){
        l.last->link = l2.first;
        l.last = l2.last;
    }
}
void NaturalMergeSort(LIST &l){
    LIST l1, l2;
    if (l.first == l.last) return;
    Init(l1);
    Init(l2);
    DistributeList(l,l1,l2);
    NaturalMergeSort(l1);
    NaturalMergeSort(l2);
    MergeList(l,l1,l2);    
}
int main(){
    LIST l;
    Init(l);
    int a[] = {12,2,8,5,1,6,4,15};
    int n = sizeof(a)/sizeof(a[0]);
    AddNumber(l,a,n);
    ShowNumber(l);
    NaturalMergeSort(l);
    ShowNumber(l);
}

When I run it, the code reports an error right at this line Segmentation Here The code still runs normally when I Debug, but when I enter the NaturalMergeSort function, in the DistributeList function, I encounter a Segmentation fault in the AddLast(l1,p) line. That's what I got in the terminal when i try to run: My Terminal I tried to fix it but it keeps getting this error many times, please help me fix it.

Answer 1

There are issues with this implementation. DistributeList is recursive, which can cause stack overflow on a large array with short runs. This can be fixed by making it iterative, alternating between L1 and L2. I also ran into data patterns where cycles were created (small circular sub-lists), which seemed to be fixed when I replaced the merge function with known working code. I don't know if the OP made similar fixes.

The questions code is not a natural merge sort. A natural merge sort is bottom up, doing a one time scan to find already sorted sub-lists, and merging them. The questions code needlessly and repeatedly scans the same values over and over. For example if the array is {14,15,12,13,10,11,8,9,6,7,4,5,2,3,0,1}, then L1 ends up with {14,15,10,11,6,7,2,3}, the scan is repeated so that L1 ends up with {14,15,6,7}, and yet again {14,15}. The same process is done for L2, to end up with {12,13}, and only then does the first merge begin.

The following is an example of a bottom up natural merge sort. A small array is used to hold pointers to the first nodes of sorted-sub-lists. apNode[i] points to a list with 2^i sorted sub-lists, or it is null. If not null, then apNode[{0 1 2 3 4 ...}] is a pointer to {1 2 4 8 16 ...} merged sub-lists. This is old code (Windows | Hungarian naming convention), but it works. A single scan at the end would be needed to set a pointer to the last node.

NODE * Merge(NODE *pNode0, NODE *pNode1)
{
NODE *pMrg;
NODE **ppMrg = &pMrg;
    if(pNode0 == NULL)                  /* if either list empty, */
        return pNode1;                  /*  return the other */
    if(pNode1 == NULL)
        return pNode0;
    while(1){                           /* merge the lists */
        if(pNode0->data <= pNode1->data){
            *ppMrg = pNode0;
            ppMrg = &(pNode0->next);
            pNode0 = *ppMrg;
            if(pNode0 == NULL){
                *ppMrg = pNode1;
                break;}}
        else{
            *ppMrg = pNode1;
            ppMrg = &(pNode1->next);
            pNode1 = *ppMrg;
            if(pNode1 == NULL){
                *ppMrg = pNode0;
                break;}}}
    return pMrg;
}

/* size of internal array */
#define ASZ 32
NODE *MergeSort(NODE * pNode)
{
NODE *apNode[ASZ] = {NULL};             /* array of lists */
NODE *pNext;
NODE *pLast;
size_t i;
    if(pNode == NULL || pNode->next == NULL)
        return pNode;
    /* merge nodes into array */
    while(pNode){
        /* set pLast to end of already sorted sub-list */
        pLast = pNode;
        while((pNext = pLast->next) != NULL && pNext->data >= pLast->data)
            pLast = pNext;
        pLast->next = NULL;
        /* merge sorted sub-list into array */
        for(i = 0; i < ASZ && apNode[i] != NULL; i++){
            pNode = Merge(apNode[i], pNode);
            apNode[i] = NULL;}
        if(i == ASZ)                    /* don't go past end array */
            i--;
        apNode[i] = pNode;
        pNode = pNext;}
    /* merge array into a single list */
    pNode = NULL;
    for(i = 0; i < ASZ; i++)
        pNode = Merge(apNode[i], pNode);
    return pNode;
}

In my benchmarking with variations of data patterns including sequences of 8 increasing numbers I don't see any significant improvement in performance versus a non-natural merge sort that merges nodes into the array one node at a time, and the natural merge sort is a bit slower for pseudo-random values.

#define ASZ 32
NODE *MergeSort(NODE * pNode)
{
NODE *apNode[ASZ] = {NULL};             /* array of lists */
NODE *pNext;
size_t i;
    if(pNode == NULL || pNode->next == NULL)
        return pNode;
    /* merge nodes into array */
    while(pNode){
        pNext = pNode->next;
        pNode->next = NULL;
        for(i = 0; i < ASZ && apNode[i] != NULL; i++){
            pNode = Merge(apNode[i], pNode);
            apNode[i] = NULL;}
        if(i == ASZ)                    /* don't go past end array */
            i--;
        apNode[i] = pNode;
        pNode = pNext;}
    /* merge array into a single list */
    pNode = NULL;
    for(i = 0; i < ASZ; i++)
        pNode = Merge(apNode[i], pNode);
    return pNode;
}