I've managed to get this working, a few things, different in C.
the declarations *&.. needed to be changed to **,
Code:
static void
list_partition( node_t *start
, node_t *split
, node_t **less_n
, node_t **grtr_n
, int32_t comp(const void *, const void *) ) {
do {
node_t *next = start->next;
if ( comp(lnode_get(start), lnode_get(split)) < 0 ) {
start->next = *less_n;
*less_n = start;
} else {
start->next = *grtr_n;
*grtr_n = start ;
}
start = next;
} while (start != NULL );
return ;
}
static node_t *
list_SQsortAux( list_t *list
, node_t **head
, int32_t comp(const void *, const void *) ) {
assert (head != NULL );
node_t *prev = NULL;
node_t *first = *head;
node_t *second = (*head)->next;
node_t *center = NULL;
node_t *less=NULL, *greatereq =NULL;
if(second != NULL ) {
prev = fakePrev (lnode_t, (*head), next );
/* find a splitter node - the first whose next item is smaller */
do {
if (comp(lnode_get(second), lnode_get(first)) < 0 ) {
/* Splitter found, first */
/*
** 1. Set center and greatereq to splitter
** 2. disconnect the spliter from list
** 3. disconnect the prior list from splitter
** 4. less than is head, can be null if splitter == head
** 5. remaining list is second
*/
greatereq = center = first ; /* 1 */
first->next = NULL; /* 2 */
prev->next = NULL; /* 3 */
less = *head ;
/* Partition the list */
list_partition(second, center, &less, &greatereq, comp );
lnode_t *const join = list_SQsortAux(list, &less, comp );
lnode_t *const last = list_SQsortAux(list, &greatereq, comp );
/* join the two sorted lists */
*head = less;
join->next = greatereq;
return last; /* Return the tail end of the list */
}
/* Still searching for splitter */
prev = first;
first = second;
second = second->next;
}while( second != NULL ) ;
}
/* Already sorted, No split node found */
return first ;
}
Thanks for your help and detailed explenation. Once I got my head around the fact that partitioning and SortAux list pointers were actually ** that made life a lot easier!
Now to implement using doubly linked lists.