struct node *merge( struct node *xs, struct node *ys )
{
    struct node *head = NULL,
                *last = NULL;

    while ( xs || ys )
    {
        struct node **l =
            ( xs && ys && xs->value < ys->value ) || ( xs && !ys ) ? &xs : &ys;

        if ( last )
            last->next = *l;

        last = *l;
        *l = ( *l )->next;

        if ( !head )
            head = last;
    }

    return head;
}

struct node *sort( struct node *head )
{
    if ( !head || !head->next )
        return head;

    struct node *mid  = head,
                *prev = NULL,
                *end  = head;

    while ( end && end->next )
    {
        prev = mid;
        mid = mid->next;
        end = end->next->next;
    }

    prev->next = NULL;

    return merge( sort( head ), sort( mid ) );
}