Hello,

My aim is to sort a double linked list.

My understanding is that the sort functions in the standard library sort arrays; to sort a linked list I need to provide my own function/s.

Rather than re-invent the wheel, I found some code that seems to work well.

Sort a Doubly Linked List using Merge Sort - Techie Delight

However the structure of the linked list in their code is as follows;
Code:
struct node
{
    int data;
    struct node *next, *prev;
};
Whereas the structure of my linked list is as follows;
Code:
struct record
{
    int data;
};
typedef struct record record_t;

struct node
{
    record_t    record;
    struct node *next;
    struct node *prev;
};
typedef struct node node_t;

struct dll
{
    node_t      *head;
    node_t      *tail;
};
typedef struct dll dll_t;
So I'm trying to modify the sample code to work with my data structure which has head/tail pointers.

The issue that I have encountered, is that the sample code accesses the linked list via a double-pointer

e.g. void mergeSort(struct node **head)

Where I access the linked list via a single-pointer
void mergeSort(dll_t *dll)
(e.g. dll->head or dll->tail)

If you compare the two mergesort functions

Original:
Code:
void mergeSort(struct node **head)
{
    // base case: 0 or 1 node
    if (*head == NULL || (*head)->next == NULL)
        return;

    // split head into 'a' and 'b' sublists
    struct node *a = *head, *b = NULL;
    split(*head, &a, &b);

    // recursively sort the sub-lists
    mergeSort(&a);
    mergeSort(&b);

    // merge the two sorted lists together
    *head = merge(a, b);
}
Attempted port:
Code:
void mergeSort(dll_t *dll)
{
    // base case: 0 or 1 node
    if (dll->head == NULL || dll->head->next == NULL)
    {
        return;
    }
    else                                      
    {
        // split list into 'a' and 'b' sublists
        node_t *a = dll->head, *b = NULL;
        node_t **head;
        *head = dll->head;

        split(*head, &a, &b)

        // sort the sub-lists
        mergeSort_sublists(&a);
        mergeSort_sublists(&b);

        // merge the two sorted lists together
        *head = merge(a, b);

    } // else (more than 1 node)
} //mergeSort
I try to set *head using
Code:
node_t **head;
*head = dll->head;
This causes an abend, so obviously not permitted.

I haven't been able to figure out why this is wrong / how to resolve.

Would appreciate some suggestions

Thanks
VW