# 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 < 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?

• 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;


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.