static struct node *merge(struct linked_list *list,
    int (*cmp)(const void *, const void *),
    struct node *left, struct node *right, size_t right_count)
{
    struct node *head;
    if(cmp(left->data, right->data) <= 0)
    {
        head = left;
        left = left->next;
    }
    else
    {
        head = right;
        struct node *node = right;
        right = right->next;
        remove_node(node, list);
        insert_before(node, list, left);
        --right_count;
    }

    while(left != right && right_count)
    {
        if(cmp(left->data, right->data) <= 0)
            left = left->next;
        else
        {
            struct node *node = right;
            right = right->next;
            remove_node(node, list);
            insert_before(node, list, left);
            --right_count;
        }
    }

    return head;
}

static struct node *mergesort(struct linked_list *list,
    int (*cmp)(const void *, const void *), struct node *head, size_t size)
{
    if(size < 2) return head;
    size_t left_count = size / 2;
    size_t right_count = size - left_count;

    struct node *tail = head;
    size_t count = left_count;
    while(count--) tail = tail->next;

    return merge(list, cmp,
        mergesort(list, cmp, head, left_count),
        mergesort(list, cmp, tail, right_count),
        right_count);
}

static void sort(struct linked_list *list,
    int (*cmp)(const void *, const void *))
{
    mergesort(list, cmp, list->first, list->size);
}