Singly Linked List of Integers (mergesort)

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

#ifndef NNODES
#define NNODES 10
#endif

typedef struct node_t {     /* list node */
    int data;
    struct node_t *next;
} node_t;

typedef struct {            /* list wrapper with head & tail pointers */
    node_t *head, *tail;
} list_t;

/** add node at end of list, update tail to end */
node_t *add (list_t *l, int v)
{
    node_t *node = malloc (sizeof *node);   /* allocate node */
    if (!node) {                            /* validate allocation */
        perror ("malloc-node");
        return NULL;
    }
    node->data = v;                         /* initialize members values */
    node->next = NULL;

    if (!l->head)                   /* if 1st node, node is head/tail */
        l->head = l->tail = node;
    else {                          /* otherwise */
        l->tail->next = node;       /* add at end, update tail pointer */
        l->tail = node;
    }

    return node;    /* return new node */
}

/* split list l into lists a & b */
void split (list_t *l, list_t *a)
{
    node_t  *pa = l->head,
            *pb = pa->next;

    while (pb) {
        pb = pb->next;
        if (pb) {
            pa = pa->next;
            pb = pb->next;
        }
    }

    a->tail = l->tail;
    l->tail = pa;

    a->head = pa->next;
    pa->next = NULL;
}

node_t *mergesorted (node_t *a, node_t *b)
{
    node_t  *res = NULL;

    /* Base cases */
    if (!a)
        return (b);
    else if (!b)
        return (a);

    /* Pick either a or b, and recur */
    // if (a->data <= b->data) {       /* ascending */
    if (a->data > b->data) {        /* descending */
        res = a;
        res->next = mergesorted (a->next, b);
    }
    else {
        res = b;
        res->next = mergesorted (a, b->next);
    }
    return (res);
}

/* sorts the linked list by changing next pointers (not data) */
void mergesort (list_t *l)
{
    list_t la;
    node_t *head = l->head;

    /* Base case -- length 0 or 1 */
    if (!head || !head->next) {
        return;
    }

    /* Split head into 'a' and 'b' sublists */
    split (l, &la);

    /* Recursively sort the sublists */
    mergesort(l);
    mergesort(&la);

    /* answer = merge the two sorted lists together */
    l->head = mergesorted (l->head, la.head);

    /* set tail pointer to last node after sort */
    for (head = l->head; head; head = head->next)
        l->tail = head;
}

/** print all nodes in list */
void prn (list_t *l)
{
    if (!l->head) {
        puts ("list-empty");
        return;
    }
    for (node_t *n = l->head; n; n = n->next)
        printf (" %d", n->data);
    putchar ('\n');
}

/** delete all nodes in list */
void del_list (list_t *l)
{
    node_t *n = l->head;
    while (n) {
        node_t *victim = n;
        n = n->next;
        free (victim);
    }
}

int main (void) {

    int arr[] = {12, 11, 10, 7, 4, 14, 8, 16, 20, 19,
                  2, 9, 1, 13, 17, 6, 15, 5, 3, 18};
    unsigned asz = sizeof arr / sizeof *arr;
    list_t l = { NULL, NULL };      /* initialize list pointers NULL */

    for (unsigned i = 0; i < asz; i++)
        add (&l, arr[i]);

    prn (&l);
    mergesort(&l);
    prn (&l);

    del_list (&l);      /* delete list (does nothing list-empty) */
}