Linked-list merge sort

node_t **mergesort(node_t **list, size_t count) {
    size_t half = count >> 1;
    if(half) {
        // Divide and recursively sort the two halves, returning links to the final
        // elements as by-products
        node_t **first_tail = mergesort(list, half);
        node_t *first_head = *list;
        node_t **second_tail = mergesort(first_tail, count - half);
        node_t *second_head = *first_tail;

        // Merge the two halves, chaining in the smaller of the two front-most
        // elements from the two lists
        for(;;) {
            // Prefer the first list in case of equality for stability
            if(first_head->key <= second_head->key) {
                *list = first_head;
                list = &first_head->next;
                // Stop once a half list has been exhausted
                if(&first_head->next == first_tail) {
                    // Chain in the rest of the second list as-is
                    *list = second_head;
                    return second_tail;
                }
                first_head = *list;
            } else {
                *list = second_head;
                list = &second_head->next;
                if(&second_head->next == second_tail) {
                    // We're ending with items from the first list so a special
                    // case is required to shuffle the final link pointing outside
                    // of list section being processed
                    *first_tail = *list;
                    *list = first_head;
                    return first_tail;
                }
                second_head = *list;
            }
        }
    }
    // Stop once there's only a single item in the list. On entry with an empty list
    // this returns invalid data, deal with that case separately if a pointer to the
    // end is required as output
    return &(*list)->next;
}