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-&gt;next = j;
      break;
    }

    if(j-&gt;val &lt; i-&gt;val) {
      if(!prev)
        ha = j;
      else
        prev-&gt;next = j;

      prev = j;
      j = j-&gt;next;
      prev-&gt;next = i;
    }
    else {
      prev = i;
      i = i-&gt;next;
    }
  }

  return ha;
}

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

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

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

  prev = mid;
  mid = mid-&gt;next;
  prev-&gt;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 &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;iterator&gt;
#include &lt;algorithm&gt;
#include &lt;list&gt;

template&lt;typename InputIt1, typename InputIt2, typename OutputIt&gt;
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 &lt; *first2) {
      *out = *first1;
      ++first1;
    }
    else {
      *out = *first2;
      ++first2;
    }
    ++out;
  }

  return std::copy(first2, end2, out);
}

template&lt;typename InputIt&gt;
void mergesort(InputIt first, InputIt end)
{
  size_t n = std::distance(first, end);
  if(n &lt; 2)
    return;
  InputIt mid = first;

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

  std::vector&lt;typename InputIt::value_type&gt; res;
  mergesort(first, mid);
  mergesort(mid, end);
  my_merge(first, mid, mid, end, std::back_inserter(res));
  std::copy(res.begin(), res.end(), first);
}

int main()
{
  std::list&lt;int&gt; a { 1,2,8,4,2457,5,2,58,3,564,6,7 };
  mergesort(a.begin(), a.end());
  for(auto&amp; i : a)
    std::cout &lt;&lt; i &lt;&lt; std::endl;
  return 0;
}


Questions:


Are there any obvious ways of improving my C++ implementation?
Are there any possible efficiency improvements? My annoyance is mostly that I walk any list twice for searching the midpoint. Is there a way of doing this without having to manually write a traversal of the list of two iterators, one moving one step at a time and the other two to get the midpoint in one sweep?
Do I have to give up generality in C++? I don't see how to do the linear "in-place merge" as with the C implementation unless we specialize. I'm not sure if it's possible to do an in-place merge of two STL lists either, since you don't have direct access to the next and previous pointers?
The loop

for(size_t i = 0; i &lt; 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 &lt; *first2) breaks the stability of merge sort. This way, if two elements compared equal, the one from the second list would output first. Very standard mistake. To fix, either compare for &lt;=, or change the order:

if (*first2 &lt; *first1) {
    *out = *first2;
    ++first2;
} else {
    *out = *first1;
    ++first1;