c - Implementing mergesort on a linked list

Question

I was tasked with implementing a merge sort algorithm on a list written in C/C++. I have the general idea down, wrote my code and have successfully compiled it. However, when I run it, it will begin fine but then hang on "prepared list, now starting sort" without giving any kind of error. I have tried to look through my code but I am at a complete loss as to what the issue could be. I am also pretty amateurish with debugging, so using gdb to the best of my abilities has lead me no where. Any advice or tips would be a tremendous help, thank you all!

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

struct listnode
{
    struct listnode *next;
    int key;
};

    //Finds length of listnode
int
findLength (struct listnode *a)
{
    struct listnode *temp = a;
    int i = 0;
    while (temp != NULL)
    {
        i++;
        temp = temp->next;
    }
    return i;
}


struct listnode *
sort (struct listnode *a)
{
    // Scenario when listnode is NULL
    if (findLength (a) <= 1)
        return a;

    //Find middle
    int mid = findLength (a) / 2;
    struct listnode *temp = a;
    struct listnode *first = a;
    struct listnode *second;

    for (int i = 0; i < mid - 1; i++)
    {
        temp = a->next;
    }
    second = temp->next;
    temp->next = NULL;

    //Recursive calls to sort lists
    first = sort (first);
    second = sort (second);

    if (first != NULL && second != NULL)
    {
        if (first->key < second->key)
        {
            a = first;
            first = first->next;
        }
        else
        {
            a = second;
            second = second->next;
        }
    }

    struct listnode *head = a;
    struct listnode *tail = a;

    while (first != NULL && second != NULL)
    {
        if (first->key < second->key)
        {
            tail = first;
            first = first->next;
            tail = tail->next;
        }
        else
        {
            tail = second;
            second = second->next;
            tail = tail->next;
        }
    }

    if (first == NULL)
    {
        while (second != NULL)
        {
            tail = second;
            second = second->next;
            tail = tail->next;
        }
    }

    while (first != NULL)
    {
        tail = first;
        first = first->next;
        tail = tail->next;
    }

    return a;
}

Here is the test code provided, written in C: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)->key = 2 * ((17 * i) % 500000);
        (space + i)->next = space + (i + 1);
    }
    (space + 499999)->next = NULL;
    node = space;
    printf ("
 prepared list, now starting sort
");
    node = sort (node);
    printf ("
 checking sorted list
");
    for (i = 0; i < 500000; i++)
    {
        if (node == NULL)
        {
            printf ("List ended early
");
            exit (0);
        }
        if (node->key != 2 * i)
        {
            printf ("Node contains wrong value
");
            exit (0);
        }
        node = node->next;
    }
    printf ("Sort successful
");
    exit (0);
}

Answer 1

You're close, but with some silly errors. Check the append operations in the merge step. They're not doing what you think they are. And of course you meant temp = temp->next; in the splitting loop.

If gdb is overwhelming, adding printf's is a perfectly fine way to go about debugging code like this. Actually you want to write a list printing function and print the sublists at each level of recursion plus the results of the merge step. It's fun to watch. Just be neat and delete all that when you're done.

Here's code that works for reference:

struct listnode *sort(struct listnode *lst) {
  if (!lst || !lst->next) return lst;
  struct listnode *q = lst, *p = lst->next->next;
  while (p && p->next) {
    q = q->next;
    p = p->next->next;
  }
  struct listnode *mid = q->next;
  q->next = NULL;
  struct listnode *fst = sort(lst), *snd = sort(mid);
  struct listnode rtn[1], *tail = rtn;
  while (fst && snd) {
    if (fst->key < snd->key) {
      tail->next = fst;
      tail = fst;
      fst = fst->next;
    } else {
      tail->next = snd;
      tail = snd;
      snd = snd->next;
    }
  }
  while (fst) {
    tail->next = fst;
    tail = fst;
    fst = fst->next;
  }
  while (snd) {
    tail->next = snd;
    tail = snd;
    snd = snd->next;
  }
  tail->next = NULL;
  return rtn->next;
}

On my old MacBook this sorts 10 million random integers in a bit over 4 seconds, which doesn't seem too bad.

You can also put the append operation in a macro and make this quite concise:

struct listnode *sort(struct listnode *lst) {
  if (!lst || !lst->next) return lst;
  struct listnode *q = lst, *p = lst->next->next;
  while (p && p->next) {
    q = q->next;
    p = p->next->next;
  }
  struct listnode *mid = q->next;
  q->next = NULL;
  struct listnode *fst = sort(lst), *snd = sort(mid);
  struct listnode rtn[1], *tail = rtn;
  #define APPEND(X) do { tail->next = X; tail = X; X = X->next; } while (0)
  while (fst && snd) if (fst->key < snd->key) APPEND(fst); else APPEND(snd);
  while (fst) APPEND(fst);
  while (snd) APPEND(snd);
  tail->next = NULL;
  return rtn->next;
}