Mergesort linked list in C++ My teacher gave us an exercise. We have to sort as quickly as possible. The fastest one gets a reward. On my own system, I am sorting 125000 words within 1.2 seconds. On my teacher's system that is 0.6s.

In my main.cpp I wrote the following code:

#include "FileStructure.h"
#include "Value.h"

template&lt;typename T&gt;
T* Merge(T* firstNode, T* secondNode)
{
  if (!firstNode) return secondNode;
  else if (!secondNode) return firstNode;

  else if (firstNode-&gt;getText() &gt;= secondNode-&gt;getText())
  {
    firstNode-&gt;setPrev(Merge(firstNode-&gt;getPrev(), secondNode));
    return firstNode;
  }
  else
  {
    secondNode-&gt;setPrev(Merge(firstNode, secondNode-&gt;getPrev()));
    return secondNode;
  }
}

template&lt;typename T&gt;
T* Split(T* my_node)
{
  if (!my_node || !my_node-&gt;getPrev()) return NULL;
  T* secondNode = my_node-&gt;getPrev();
  my_node-&gt;setPrev(secondNode-&gt;getPrev());
  secondNode-&gt;setPrev(Split(secondNode-&gt;getPrev()));
  return secondNode;
}

template&lt;typename T&gt;
T* MergeSort(T* my_node)
{
  if (!my_node) return NULL;
  else if (!my_node-&gt;getPrev()) return my_node;
  return Merge(MergeSort(my_node), MergeSort(Split(my_node)));
}


int main(void)
{
  FileStructure f;
  Key* head = new Key();
  f.loadFile("data/gibberish.bin", *head);

  head = MergeSort(head);
  Key* tempHead = head; //values

  while (tempHead)
  {
    tempHead-&gt;setValuePtr(MergeSort(tempHead-&gt;getValuePtr()));
    tempHead = tempHead-&gt;getPrev();
  }
  // save sorted data into a new file called sorted.bin
  f.saveFile(*head, "sorted.bin");

  delete head;
  //newHead = NULL;

  return 0;
}


The key.h and value.h only have getters and setters. Key also has another method called AddValue(). 

This one is:

void Key::addValue(std::string word)
{
    if (key == word.substr(0, 2))
    {
        Value *temp = valueTail;
        valueTail = new Value(word);
        valueTail-&gt;setPrev(temp);
        return;
    }
    else if (prevKey)
    {
        prevKey-&gt;addValue(word);
        return;
    }
    prevKey = new Key();
    prevKey-&gt;setText(word.substr(0, 2));
    prevKey-&gt;valueTail = new Value(word);
}


All the other functions are inline functions. 
As you can see it's dirty code. I removed as much as possible variables. I think it can be faster, but I don't know how.

I ran Gprof on my code:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  us/call  us/call  name    
 72.73      0.24     0.24                             Key::addValue(std::string)
 12.12      0.28     0.04   151883     0.26     0.26  Value* Split&lt;Value&gt;(Value*)
  9.09      0.31     0.03   151883     0.20     0.20  Value* Merge&lt;Value&gt;(Value*, Value*)
  6.06      0.33     0.02      522    38.31    38.31  Value::~Value()
  0.00      0.33     0.00      522     0.00     0.00  Key* Merge&lt;Key&gt;(Key*, Key*)
  0.00      0.33     0.00      522     0.00     0.00  Key* Split&lt;Key&gt;(Key*)


Help me out please!
Btw: I have no memory leaks, thanks to valgrind.
I had a similar contest in high school.  I decided to win in every category :)

In modern architectures, linked lists are slow.  See https://www.youtube.com/watch?v=YQs6IC-vgmo for example.  Does it need to be a linked list?  Does it need to be a merge sort in particular?  I can advice more specifically if you update your post to add that info.

Even though it would not be a legal entry, you might try using a std::vector&lt;std::string&gt; and just calling std::sort and using that speed as a baseline!


  Btw: I have no memory leaks, thanks to valgrind. 


That is a heroic effort to achieve something that should normally be the case in C++.  Use unique_ptr and general RAII techniques, and memory leaking in a single-threaded program is simply not an issue to worry about!  That is, you are making it too hard.

Read through and bookmark the C++ Standard Guidelines.  Numbers I note later are citations from this.



Use the proper #include files.  You have a couple project-specific includes, but no standard library stuff; maybe you are not using anything from the library, not even language-support features?  But that will change if you improve the code.



template&lt;typename T&gt;
T* Merge(T* firstNode, T* secondNode)
{
  if (!firstNode) return secondNode;
  else if (!secondNode) return firstNode;

  else if (firstNode-&gt;getText() &gt;= secondNode-&gt;getText())
  {
    firstNode-&gt;setPrev(Merge(firstNode-&gt;getPrev(), secondNode));
    return firstNode;
  }
  else
  {
    secondNode-&gt;setPrev(Merge(firstNode, secondNode-&gt;getPrev()));
    return secondNode;
  }
}


So let’s see… you are taking a couple node pointers, not any kind of abstraction as the linked list as a collection?  I understand if this is the kind of stuff you are learning, but it is hard to follow as it is not “normal” programming.

So far, I see some good habits.  C++ (not C) style placement of the *, use of contextual conversion to bool as a truth test of the pointer, putting quick-return tests at the very top, in a compact manner … all very mature style!

The logic looks like straight functional programming style.  Good for Haskell, not good for C++.  I don’t think the compiler can do tail recursion elimination here.  You will run out of stack space if your list is long!

Writing this as a loop rather than recursively will make it faster and avoid the size limit.



template&lt;typename T&gt;
T* Split(T* my_node)
{
  if (!my_node || !my_node-&gt;getPrev()) return NULL;
  T* secondNode = my_node-&gt;getPrev();
  my_node-&gt;setPrev(secondNode-&gt;getPrev());
  secondNode-&gt;setPrev(Split(secondNode-&gt;getPrev()));
  return secondNode;
}


Forget that the NULL macro ever existed!  Banish it from your memory.  C++ has the special nullptr value.

Again, I see a good habit:  declared secondNode when you were ready to initialize it.



template&lt;typename T&gt;
T* MergeSort(T* my_node)
{
  if (!my_node) return NULL;
  else if (!my_node-&gt;getPrev()) return my_node;
  return Merge(MergeSort(my_node), MergeSort(Split(my_node)));
}


As before, nullptr, not NULL.

It looks like you are peeling off one node at a time, not cutting the list in half.  If I follow this right, you have implemented an insertion sort where you need a linear search over the list to find the insertion position, not a proper merge sort.  Each item will have to compare (on average) with half of the items processed already.  This is O(n²).  A proper merge will compare once for each item in the shorter list, recursively sorting the half-lists first.  That is O(n log n).

Now I’m sure you know that the “big O” will trump the linear speedup of any of the steps!



int main(void)
{
  FileStructure f;
  Key* head = new Key();
  f.loadFile("data/gibberish.bin", *head);

  head = MergeSort(head);
  Key* tempHead = head; //values

  while (tempHead)
  {
    tempHead-&gt;setValuePtr(MergeSort(tempHead-&gt;getValuePtr()));
    tempHead = tempHead-&gt;getPrev();
  }
  // save sorted data into a new file called sorted.bin
  f.saveFile(*head, "sorted.bin");

  delete head;
  //newHead = NULL;

  return 0;
}


Don’t write (void) for an empty parameter list!  Stroustrup calls that “an abomination”.  It is supported so that it can read C header files; but you should not write that in C++, ever.

  Key* head = new Key();


⧺C.149 — no naked new or delete.

You should probably make this a unique_ptr as a drop-in replacement without otherwise changing the architecture.

  while (tempHead)
  {
    tempHead-&gt;setValuePtr(MergeSort(tempHead-&gt;getValuePtr()));
    tempHead = tempHead-&gt;getPrev();
  }


I don’t understand that part.  You sorted with the call to MergeSort, right?  Why do you have to back up a node and sort it again?  This might be a work-around for a problem with the sorting or the data structure.

Then you treat the original node,  head, as the sorted list’s head?  So what was the deal with tempHead?



void Key::addValue(std::string word)
{
    if (key == word.substr(0, 2))
    {
        Value *temp = valueTail;
        valueTail = new Value(word);
        valueTail-&gt;setPrev(temp);
        return;
    }
    else if (prevKey)
    {
        prevKey-&gt;addValue(word);
        return;
    }
    prevKey = new Key();
    prevKey-&gt;setText(word.substr(0, 2));
    prevKey-&gt;valueTail = new Value(word);
}


You are taking the string word by value, copying it into the function.  You don’t modify word, right?

I don’t know what Value is, or why you don’t just store the std::string in your nodes.

substr is not a normal or good way to manipulate strings in the standard library.  If I knew what you were trying to do, I could advise how it should naturally be done.



Good luck to you!  Keep at it.