Sorting function that also works with containers having only forward iterators

Question

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 < i->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 <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <list>
template<typename InputIt1, typename InputIt2, typename OutputIt>
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 < *first2) {
 *out = *first1;
 ++first1;
 }
 else {
 *out = *first2;
 ++first2;
 }
 ++out;
 }
 return std::copy(first2, end2, out);
}
template<typename InputIt>
void mergesort(InputIt first, InputIt end)
{
 size_t n = std::distance(first, end);
 if(n < 2)
 return;
 InputIt mid = first;
 for(size_t i = 0; i < n/2; ++i)
 ++mid;
 std::vector<typename InputIt::value_type> 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<int> a { 1,2,8,4,2457,5,2,58,3,564,6,7 };
 mergesort(a.begin(), a.end());
 for(auto& i : a)
 std::cout << i << std::endl;
 return 0;
}

Questions:

1. Are there any obvious ways of improving my C++ implementation?

2. 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?

3. 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?

Answer 1

• 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 < *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 <=, or change the order:

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

Answer 2

std::distance may (probably will) be linear for a std::list. You could determine it once and pass it down. Don't forget that for odd length lists one of them is n/2 and the other n/2+1.

If the list is long allocating a vector may be expensive:

std::vector<typename InputIt::value_type> res;

You're working recursively remember so will have vectors of size n , n /2 , n/ 4 , .. allocated at the same time so end up with 2*n additional space allocated. And in fact create and destroy n*n the space (doing two recursions at each step).

You should look at std::splice which can be used to transfer between lists without creating or destroying values. That may not sound like a big deal for a storage type of int but as a general purpose template could be time consuming. Regardless the container is allocating and deallocating 'links' somewhere back there!

I would at least work 'destructively' removing from one list and adding to the result.

At the end you would have an empty original list and a nicely sorted result. You could then perform an std::swap(.,.).

If you're not prepared to change your function prototype (my idea requires you to pass in the list not just iterators) it is probably still worth copying the values out into a temporary list, doing it my way and copy the values back again!

You can take a bit of pressure off by reserve(.) on your vector since you know the required capacity. But as I said, I'm not sure it's right vehicle.