4
\$\begingroup\$

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?

\$\endgroup\$
4
\$\begingroup\$
  • 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;
    
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.