qsort on linked lists in C - from https://www.reddit.com/r/C_Programming/comments/acggdj/qsort_linked_lists/

qsort.c

/* A simple qsort implementation on linked lists */
 
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
 
/*
 * A 'node' is an element of the linked list, containing a pointer
 * to the next element, and the associated data
 * A full list is represented by a pointer to its first element
 * (hence a list and a node are not different types)
 * Empty lists are represented by NULL pointers
 * Functions mutating lists will take 'node **', so the can update the caller
 *
 * Note : this is an "intrusive" list, as the data is in the list node itself
 * Note2: linked lists are very inefficient on modern computers
 */
typedef struct node
{
    struct node *next;  /* The next element */
    int data;           /* The associated data */
} node;
 
/*
 * Appends a single element at the head of the list
 * List is passed by address, so the content of the caller
 * variable is updated to point to the new head
 *
 * Complexity: O( 1 )
*/
void list_add_node( node **list, node *node )
{
    node->next = *list;
    *list = node;
}
 
/*
 * Append list at the end of another list
 * Head list is passed by address, so the content of the caller
 * variable can be updated to poin to the new head
 * if the original list was empty (NULL)
 *
 * Complexity: O( len(l0) )
 */
void list_concat( node **l0, node *l1 )
{
    /* We find the address of the pointer that needs to be updated */
    while (*l0)
        l0 = &((*l0)->next);
   
    /* We update it to point to the new tail */
    *l0 = l1;
}
 
/*
 * Quick sort of the list
 * This is a naive quicksort implementation:
 * a) It will decay into n^2 complexity if the list is already sorted
 * b) It scans the list multiple time to concatenate
 *    (this can easily be avoided by keeping track of the address of the end of left)
 *
 * Complexity:
 *   best     : O( len(list) )
 *   average  : O( len(list)*log(len(list)) )
 *   worst    : O( len(list)^2 )
 */
void my_qsort( node **list )
{
    /* Sorting an empty list is trivial */
    if (!*list)
        return;
 
    /* Extract the pivot */    
    node *pivot = *list;
    int data = pivot->data;
    node *p = pivot->next;
    pivot->next = NULL;
 
    /* Construct left and right lists in place in a single pass*/
    node *left = NULL;
    node *right = NULL;
 
    while (p)
    {
        node *n = p;  
        p = p->next;
        if (n->data<data)
            list_add_node( &left, n );
        else
            list_add_node( &right, n );
    }
 
    /* We now sort left and right */
    /* If left and right are of vastly different lengths, the complexity won't be O(n log n) */
    my_qsort( &left );
    my_qsort( &right );
 
    /* We now concatenate lists [this is inefficient, but doesn't hurt complexity] */
    node *result = NULL;
    list_concat( &result, left );
    list_concat( &result, pivot );
    list_concat( &result, right );
    *list = result;
}
 
/*
 * Allocate a new node, with the specified next pointer and data
 */
node *list_make_node( node *next, int data )
{
    node *n = malloc( sizeof(node) );
    n->next = next;
    n->data = data;
 
    return n;
}
 
/*
 * Frees a list
 * Note that we pass the address of the list, so the caller's variable
 * is properly set to NULL after execution.
 */
void list_free( node **list )
{
    while (*list)
    {
        node *node = *list;
        *list = (*list)->next;
        free( node );
    }
 
    /* Exiting the loop ensure *list is NULL, and the caller had its variable updated */
}
 
/*
 * Returns true or false if a list is ordered or not
 * This is strictly a utility function and is not used in sorting
 * Complexity: O( len(list) )
 */
bool list_is_ordered( node *list )
{
    bool first = true;
    int data;
    while (list)
    {
        if (first)
        {
            data = list->data;
            first = false;
        }
        else
        {
            if (list->data<data)
                return false;
            data = list->data;
        }
        list = list->next;
    }
    return true;
}
 
/*
 * Utility to display a list.
 */
void list_display( node *list )
{
    printf( "%s IN ORDER : ", list_is_ordered(list)?"":"NOT" );
    while (list)
    {
        printf( "%d ", list->data );
        list = list->next;
    }
    printf( "\n" );
}
 
/*
 * Main takes a single optional argument: the length of the list to be sorted
 */
int main( int argc, char **argv )
{
    /* How many node to we create */
    size_t count = 50;
    if (argc==2)
        count = atoi( argv[1] );
   
    /* Building initial data */
    node *list = NULL;
    while (count--)
    {
        list = list_make_node( list, random() );
    }
 
    /* Display */
    list_display( list );
 
    /* Sorting */
    my_qsort( &list );
    // my_qsort( &list );
 
    /* Display */
    list_display( list );
 
    if (!list_is_ordered(list))
        return EXIT_FAILURE;
 
    list_free( &list );
 
    return EXIT_SUCCESS;
}