{									\
  if (l_left == NULL)							\
    return l_right;							\
  else if (l_right == NULL)						\
    return l_left;							\
									\
  LTYPE *l_out = NULL, *l_last = NULL;					\
									\
  LTYPE *l_l = l_left, *l_r = l_right;					\
  while (l_l != NULL && l_r != NULL)					\
    {									\
      int cmp = fn_cmp (l_l, l_r);					\
      if (cmp <= 0)							\
	l_l = LTYPE##_merge_sort_out_append_ (&l_out, &l_last, l_l);	\
      else								\
	l_r = LTYPE##_merge_sort_out_append_ (&l_out, &l_last, l_r);	\
    }									\
									\
  LTYPE *l_remaining = (l_l != NULL) ? l_l : l_r;			\
  while (l_remaining != NULL)						\
    l_remaining =							\
      LTYPE##_merge_sort_out_append_ (&l_out, &l_last, l_remaining);	\
									\
  return l_out;								\
}

/* Merge sort implementation taking the first node of the list to sort,
   and the comparison function. Returns the first node of the sorted list.
   Note: use this if you don't care about updating the information in the
   wrapper.  */
#define _MERGE_SORT_DEFN_SORT(LTYPE, EXPORT)				\
EXPORT LTYPE *								\
LTYPE##_merge_sort_ (LTYPE *node,					\
		     int (*fn_cmp)(const LTYPE *, const LTYPE *))	\
{									\
  if (node == NULL)							\
    return NULL;							\
  else if (node->next == NULL)						\
    return node;							\
									\
  LTYPE *left_end = LTYPE##_merge_sort_compute_turtle_ (node);		\
  LTYPE *left_begin = node;						\
  LTYPE *right_begin = left_end->next;					\
  /* break the list. */							\
  left_end->next = NULL;						\
  right_begin->prev = NULL;						\
									\
  left_begin = LTYPE##_merge_sort_ (left_begin, fn_cmp);		\
  right_begin = LTYPE##_merge_sort_ (right_begin, fn_cmp);		\
  return LTYPE##_merge_sort_merge_ (left_begin, right_begin, fn_cmp);	\
}

/* Merge sort wrapper that the end-user should be using as it updates the
   first and last metadata of the list in wrapper as well.
   If the user does not want to pay the cost of the update of the data,
   it can directly use _##LTYPE##_merge_sort_merge.  */
#define _MERGE_SORT_DEFN_WRAPPER_SORT(LWRAPPERTYPE, LTYPE, EXPORT)	\
EXPORT void								\
LTYPE##_merge_sort (LWRAPPERTYPE *wrapper,				\
		    int (*fn_cmp) (const LTYPE *, const LTYPE *))	\
{									\
  wrapper->first = LTYPE##_merge_sort_ (wrapper->first, fn_cmp);	\
									\
  if (wrapper->first == NULL || wrapper->first->next == NULL)		\
    wrapper->last = wrapper->first;					\
  else									\
    for (LTYPE *node = wrapper->first;					\
	 node != NULL;							\
	 node = node->next)						\
      wrapper->last = node;						\
}

#define LINKED_LIST_MERGE_SORT_DECL(LWRAPPERTYPE, LTYPE, EXPORT)	\
  _MERGE_SORT_IMPL_COMPUTE_TURTLE(LTYPE)				\
  _MERGE_SORT_IMPL_OUT_APPEND(LTYPE)					\
  _MERGE_SORT_IMPL_MERGE(LTYPE)						\
  _MERGE_SORT_DEFN_SORT(LTYPE, EXPORT)					\
  _MERGE_SORT_DEFN_WRAPPER_SORT(LWRAPPERTYPE, LTYPE, EXPORT)

#endif /* _DOUBLY_LINKED_LIST_H */