Mergesort function on linked-list using only one function

Question

I'm fairly terrible at coding and I need to write the function: struct listnode * mergesort(struct listnode *data) in either C or C++, but test code is in C.

main() consist of the testing code to test the function. This is given by the professor

I can compile this, but when I run it, it gives me

prepared list, now starting sort

Process returned -1073741571 (0xC00000FD) execution time: 1.034 s

It won't go past that point, so surely there's something wrong with my function but I'm not sure what it is.

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


struct listnode { struct listnode * next;
                  long              value; } ;


//This is the function I need to write:
struct listnode * mergesort(struct listnode *data)
{  
    if (data == NULL)
        return NULL;
    ///////Find the location of mid

    struct listnode *pRunToEnd = data;
    struct listnode *pRunToMid = data;
    struct listnode *pPreMid = NULL;
    while (pRunToEnd != NULL)
    {
        pRunToEnd = pRunToEnd->next;
        while (pRunToEnd!=NULL){
            pRunToEnd = pRunToEnd->next;
            if (pRunToEnd!=NULL){
                pRunToEnd = pRunToEnd->next;
        pPreMid = pRunToMid;
        pRunToMid = pRunToMid->next; }
        }
    }
    //////////Cut the list into 2 half
    if (pPreMid != NULL)
        pPreMid->next = NULL;
    /////Recursion
    mergesort(data);
    mergesort(pRunToMid);

    //////////Combine 2 half
    struct listnode *pFirst = data;
    struct listnode *pPreFirst = NULL;
    pPreMid = NULL;
    while (pFirst != NULL && pRunToMid!= NULL)
    {
        if(pFirst->value > pRunToMid->value)
        {
            pPreFirst = pFirst;
            pFirst = pFirst->next;
        }
        else
        {
            /////Chain the element of first list
            pPreFirst->next = pRunToMid;
            pPreMid = pRunToMid;
            pRunToMid = pRunToMid->next;
            pPreMid->next = NULL;
        }
    }

    ///////////////Chain the rest of second list
    if (pFirst == NULL)
    {
        pPreFirst->next = pRunToMid;
    }

    //////if pRunToMid is NULL, we do nothing because we have merged all elements in second list into first
    return(pPreFirst);


}


int main(void)
{
   long i;
   struct listnode *node, *tmpnode, *space;
   space =  (struct listnode *) malloc( 500000*sizeof(struct listnode));
   for( i=0; i< 500000; i++ )
   {  (space + i)->value = 2*((17*i)%500000);
      (space + i)->next = space + (i+1);
   }
   (space+499999)->next = NULL;
   node = space;
   printf("\n prepared list, now starting sort\n");
   node = mergesort(node);
   printf("\n checking sorted list\n");
   for( i=0; i < 500000; i++)
   {  if( node == NULL )
      {  printf("List ended early\n"); exit(0);
      }
      if( node->value != 2*i )
      {  printf("Node contains wrong value\n"); exit(0);
      }
      node = node->next;
   }
   printf("Sort successful\n");
   exit(0);
}

Answer 1

Some things are wrong.

1. A check for the base case of a list with one element is missing. For that purpose you could change

       if (data == NULL)
           return NULL;
   

   to

       if (!data || !data->next)   // zero or one element list: already sorted
           return data;
   

2. The loop to Find the location of mid is faulty; change it to

       while (pRunToEnd)
       {
           if (pRunToEnd = pRunToEnd->next)
               pRunToEnd = pRunToEnd->next;
           pPreMid = pRunToMid;
           pRunToMid = pRunToMid->next;
       }
   

3. As rpattiso wrote, you should be using the return value of mergesort(data) and mergesort(pRunToMid) as the new heads of the sorted lists, so change

       mergesort(data);
       mergesort(pRunToMid);
   

   to

       data = mergesort(data);
       pRunToMid = mergesort(pRunToMid);
   

4. The relational operator is backwards - change

           if(pFirst->value > pRunToMid->value)
   

   to

           if (pFirst->value < pRunToMid->value)
   

5. In the else block of the merge loop, where you want to insert an element of the second list into the first, you forgot to handle the case where the element of the second list is to be inserted at the head of the first (i. e., becomes the new head of the list), as well as to update the preceding element pointer pPreFirst, and you didn't properly set the pointer ->next for chaining to the first list. Change the block to

           {
               if (!pPreFirst) // no preceding element
                   data = pRunToMid;   // new list head
               else
                   pPreFirst->next = pRunToMid;    /////Chain the element of first list
               pPreFirst = pRunToMid;  // update pointer to preceding element
               pRunToMid = pRunToMid->next;
               pPreFirst->next = pFirst;   // chain to first list
           }
   

6. You were returning the tail of the sorted list instead of its head. Change

       return(pPreFirst);
   

   to

       return data;