Sorting function that also works with containers having only forward iterators

I was playing around with some code trying to implement a sorting algorithm in C++ that also works with singly linked lists. Since the merge routine of mergesort only scans forward, implementing a generic mergesort seemed like the way to go.

In C, I would have implemented it as follows:

typedef struct node {
  int val;
  struct node *next;
} node_t;

/* Merges two sorted linked lists placing the result in the
   first list. The function modifies both lists */
node_t* merge(node_t *ha, node_t *hb)
{
  if(!ha)
    return hb;
  if(!hb)
    return ha;

  node_t *i;
  node_t *prev;
  node_t *j = hb;

  prev = NULL;
  i = ha;
  while(i || j) {
    if(!j) break;
    if(!i) {
      prev->next = j;
      break;
    }

    if(j->val val) {
      if(!prev)
        ha = j;
      else
        prev->next = j;

      prev = j;
      j = j->next;
      prev->next = i;
    }
    else {
      prev = i;
      i = i->next;
    }
  }

  return ha;
}

node_t* mergesort(node_t *ha)
{
  if(!ha || !ha->next)
    return ha;

  node_t * prev;
  node_t *mid = ha;
  node_t *fast = ha;

  /* Find midpoint of linked list */
  while(1) {
    fast = fast->next;
    if(!fast) break;
    fast = fast->next;
    if(!fast) break;
    mid = mid->next;
  }

  prev = mid;
  mid = mid->next;
  prev->next = NULL;
  ha = mergesort(ha);
  mid = mergesort(mid);
  return merge(ha, mid);
}

Here is my C++ implementation, which I would like to have reviewed:

```
#include
#include
#include
#include
#include

template
OutputIt my_merge(InputIt1 first1,
InputIt1 end1,
InputIt2 first2,
InputIt2 end2,
OutputIt out)
{
while(first1 != end1) {
if(first2 == end2)
return std::copy(first1, end1, out);

if(*first1
void mergesort(InputIt first, InputIt end)
{
size_t n = std::distance(first, end);
if(n res;
mergesort(first, mid);
mergesort(mid, end);
my_merge(first, mid, mid, end, std::back_inserter(res));
std::copy(res.beg

-
The loop

for(size_t i = 0; i < n/2; ++i)
    ++mid;

may and should be replaced with std::advance(mid, n/2)

To answer your question on better ways of finding the midpoint, I don't think it is worthy: it complicates the logic, while the amount of calculation remains the same.

-
A condition `if(*first1

StackExchange Code Review Q#75745, answer score: 4