C++ Template Singly-Linked List w/Sort

#include <iostream>
#include <iomanip>

/* linked list node */
template <class T>
struct node_t {
    T data;
    node_t<T> *next;
};

/* default compare function for types w/overload (ascending) */
template <typename T>
int compare_asc (const node_t<T> *a, const node_t<T> *b)
{
    return (a->data > b->data) - (a->data < b->data);
}

/* compare function for types w/overload (descending) */
template <typename T>
int compare_desc (const node_t<T> *a, const node_t<T> *b)
{
    return (a->data < b->data) - (a->data > b->data);
}

template <class T>
class list_t {
    node_t<T> *head, *tail;
    int (*cmp)(const node_t<T>*, const node_t<T>*);
    /* merge lists after mergesort_start */
    node_t<T> *mergesorted (node_t<T> *a, node_t<T> *b);
    void mergesort_run (list_t<T> *l);      /* mergesort function */

    public:
    list_t (void);                          /* constructors */
    list_t (int(*f)(const node_t<T>*, const node_t<T>*));
    ~list_t (void);                         /* destructor */
    list_t (const list_t&);                 /* copy constructor */
    /* setter for compare function */
    void setcmp (int (*f)(const node_t<T>*, const node_t<T>*));

    node_t<T> *addnode (T data);            /* simple add at end */
    node_t<T> *addinorder (T data);         /* add in order */
    void delnode (T data);                  /* delete node */
    void prnlist (const char *delim = " "); /* print delim separated */
    void prnfixed (const size_t w = 4, const char *delim = " ");

    list_t split (void);                    /* split list ~ 1/2 */
    void join (list_t<T>&l);                /* join list l at end */

    void insertionsort (void);              /* insertion sort list */
    void mergesort (void);                  /* wrapper for mergesort */
};

/* constructor (default) */
template <class T>
list_t<T>::list_t (void)
{
    head = tail = nullptr;
    cmp = compare_asc;
}

/* constructor taking compare function as argument */
template <class T>
list_t<T>::list_t (int(*f)(const node_t<T>*, const node_t<T>*))
{
    head = tail = nullptr;
    cmp = f;
}

/* destructor free all list memory */
template <class T>
list_t<T>::~list_t (void)
{
    node_t<T> *pn = head;
    while (pn) {
        node_t<T> *victim = pn;
        pn = pn->next;
        delete victim;
    }
}

/* copy ctor - copy exising list */
template <class T>
list_t<T>::list_t (const list_t& l)
{
    cmp = l.cmp;                        /* assign compare function ptr */
    head = tail = nullptr;              /* initialize head/tail */

    /* copy data to new list */
    for (node_t<T> *pn = l.head; pn; pn = pn->next)
        this->addnode (pn->data);
}

/* setter compare function */
template <class T>
void list_t<T>::setcmp (int(*f)(const node_t<T>*, const node_t<T>*))
{
    cmp = f;
}


/* add using tail ptr */
template <class T>
node_t<T> *list_t<T>::addnode (T data)
{
    node_t<T> *node = new node_t<T>;        /* allocate/initialize node */
    node->data = data;
    node->next = nullptr;

    if (!head)
        head = tail = node;
    else {
        tail->next = node;
        tail = node;
    }

    return node;
}

template <class T>
node_t<T> *list_t<T>::addinorder (T data)
{
    if (!cmp) {     /* validate compare function not nullptr */
        std::cerr << "error: compare is nullptr.\n";
        return nullptr;
    }

    node_t<T> *node = new node_t<T>;        /* allocate/initialize node */
    node->data = data;
    node->next = nullptr;

    node_t<T> **ppn = &head,                /* ptr-to-ptr to head */
              *pn = head;                   /* ptr to head */

    while (pn && cmp (node, pn) > 0) {      /* node sorts after current */
        ppn = &pn->next;                    /* ppn to address of next */
        pn = pn->next;                      /* advance pointer to next */
    }

    node->next = pn;                        /* set node->next to next */
    if (pn == nullptr)
        tail = node;
    *ppn = node;                            /* set current to node */

    return node;                            /* return node */
}

template <class T>
void list_t<T>::delnode (T data)
{
    node_t<T> **ppn = &head;        /* pointer to pointer to node */
    node_t<T> *pn = head;           /* pointer to node */

    for (; pn; ppn = &pn->next, pn = pn->next) {
        if (pn->data == data) {
            *ppn = pn->next;        /* set address to next */
            delete pn;
            break;
        }
    }
}

template <class T>
void list_t<T>::prnlist (const char *delim)
{
    if (!head) {
        std::cout << "empty-list\n";
        return;
    }
    for (node_t<T> *pn = head; pn; pn = pn->next)
        pn == head ? std::cout << pn->data : std::cout << delim << pn->data;
    std::cout << '\n';
}

template <class T>
void list_t<T>::prnfixed (const size_t w, const char *delim)
{
    size_t c = 0;

    if (!head) {
        std::cout << "empty-list\n";
        return;
    }
    for (node_t<T> *pn = head; pn; pn = pn->next, c++) {
        if (c && c % 20 == 0)
            std::cout << '\n';
        // pn == head ? std::cout << std::setw(w) << pn->data : std::cout << delim << std::setw(w) << pn->data;
        std::cout << delim << std::setw(w) << pn->data;
    }
    std::cout << '\n';
}

/* split list l into lists a & b */
template <class T>
list_t<T> list_t<T>::split (void)
{
    list_t<T> s;                /* new instance of class */

    node_t<T> *pa = head,       /* pointer to current head */
            *pb = pa->next;     /* 2nd pointer to double-advance */

    while (pb) {                /* while not end of list */
        pb = pb->next;          /* advance 2nd ptr */
        if (pb) {               /* if not nullptr */
            pa = pa->next;      /* advance current ptr */
            pb = pb->next;      /* advance 2nd ptr again */
        }
    }

    s.tail = tail;              /* 2nd half tail will be current tail */
    tail = pa;                  /* current tail is at pa */

    s.head = pa->next;          /* 2nd half head is next ptr */
    pa->next = nullptr;         /* set next ptr NULL to end 1st 1/2 */

    return s;                   /* return new instance */
}

/** join two lists setting head to nullptr
 *  on the list that was joined to prevent destructor
 *  from being called.
 */
template <class T>
void list_t<T>::join (list_t<T>&l) {
    this->tail->next = l.head;
    this->tail = l.tail;
    l.head = nullptr;
}

/** insertion sort of linked list.
 *  re-orders list in sorted order.
 */
template <class T>
void list_t<T>::insertionsort (void)
{
    if (!cmp) {     /* validate compare function not nullptr */
        std::cerr << "error: compare is nullptr.\n";
        return;
    }

    node_t<T> *sorted = head,       /* initialize sorted list to 1st node */
              *pn = head->next;     /* advance original list node to next */

    sorted->next = NULL;            /* initialize sorted->next to NULL */

    while (pn) {                    /* iterate over existing from 2nd node */
        node_t<T> **pps = &sorted,  /* ptr-to-ptr to sorted list */
                *ps = *pps,         /* ptr to sorted list */
                *next = pn->next;   /* save list next as separate pointer */

        while (ps && cmp(ps, pn) < 0) {  /* loop until sorted */
            pps = &ps->next;        /* get address of next node */
            ps = ps->next;          /* get next node pointer */
        }

        *pps = pn;          /* insert existing in sort order as current */
        pn->next = ps;      /* set next as sorted next */
        pn = next;          /* reinitialize existing pointer to next */
    }

    head = sorted;          /* update head to sorted head */

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

/** merge sublists in sort order */
template <class T>
node_t<T> *list_t<T>::mergesorted (node_t<T> *a, node_t<T> *b)
{
    node_t<T> *result = nullptr;

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

    /* Pick either a or b, and recur */
    // if (a->data <= b->data) {
    // if (compare_asc (a, b) <= 0) {
    if (cmp (a, b) <= 0) {
        result = a;
        result->next = mergesorted (a->next, b);
    }
    else {
        result = b;
        result->next = mergesorted (a, b->next);
    }

    return result;
}

/* split list into sublists to be sorted when merged */
template <class T>
void list_t<T>::mergesort_run (list_t<T> *l)
{
    /* Base case -- length 0 or 1 */
    if (!l->head || !l->head->next) {
        return;
    }

    /* Split head into 'a' and 'b' sublists */
    list_t<T> la = l->split();

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

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

    /* set la.head NULL to prevent destructor from running */
    la.head = nullptr;
}

template <class T>
void list_t<T>::mergesort(void)
{
    if (!cmp) {     /* validate compare function not nullptr */
        std::cerr << "error: compare is nullptr.\n";
        return;
    }

    mergesort_run (this);

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

int main (void) {

    list_t<int> l;

    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;

    for (unsigned i = 0; i < asz; i++)
        l.addnode (arr[i]);

    l.prnlist();
#ifndef INSSORT
    l.mergesort();
#else
    l.insertionsort();
#endif
    l.prnlist();

    l.setcmp (compare_desc);
#ifndef INSSORT
    l.mergesort();
#else
    l.insertionsort();
#endif
    l.prnlist();
}