Mergesort single linked list (improvements from SE answer)

linked_list_sort.c

/* Originally from: http://stackoverflow.com/a/27663998/432509
 *
 * With following modifications: 
 * - Use a pointer to the tail (remove 2x conditional checks, reduces code-size).
 * - Avoid re-assigning empty values the size doesn't change.
 * - Corrected comments.
 */

static void *listbase_sort_impl(struct Link *head, int (*cmp)(const void *, const void *))
{
	int block_size = 1, block_count;
	do {
		/* Maintain two lists pointing to two blocks, 'l' and 'r' */
		struct Link *l = head, *r = head, **tail_p;

		head = NULL; /* Start a new list */
		tail_p = &head;

		block_count = 0;

		/* Walk through entire list in blocks of 'block_size'*/
		while (l != NULL) {
			/* Move 'r' to start of next block, measure size of 'l' list while doing so */
			int l_size, r_size = block_size;

			block_count++;
			for (l_size = 0; (l_size < block_size) && (r != NULL); l_size++) {
				r = r->next;
			}

			/* Merge two list until their individual ends */
			bool l_empty = (l_size == 0);
			bool r_empty = (r_size == 0 || r == NULL);
			while (!l_empty || !r_empty) {
				struct Link *s;
				/* Using <= instead of < gives us sort stability */
				if (r_empty || (!l_empty && cmp(l, r) <= 0)) {
					s = l;
					l = l->next;
					l_size--;
					l_empty = (l_size == 0);
				}
				else {
					s = r;
					r = r->next;
					r_size--;
					r_empty = (r_size == 0) || (r == NULL);
				}

				/* Update new list */
				(*tail_p) = s;
				tail_p = &(s->next);
			}

			/* 'r' now points to next block for 'l' */
			l = r;
		}

		/* terminate new list, take care of case when input list is NULL */
		*tail_p = NULL;

		/* Lg n iterations */
		block_size <<= 1;

	} while (block_count > 1);

	return head;
}