# 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<typename T>
T* Merge(T* firstNode, T* secondNode)
{
if (!firstNode) return secondNode;
else if (!secondNode) return firstNode;

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

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

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

int main(void)
{
FileStructure f;

{
}
// save sorted data into a new file called sorted.bin

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->setPrev(temp);
return;
}
else if (prevKey)
{
return;
}
prevKey = new Key();
prevKey->setText(word.substr(0, 2));
prevKey->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
12.12      0.28     0.04   151883     0.26     0.26  Value* Split<Value>(Value*)
9.09      0.31     0.03   151883     0.20     0.20  Value* Merge<Value>(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<Key>(Key*, Key*)
0.00      0.33     0.00      522     0.00     0.00  Key* Split<Key>(Key*)


Help me out please! Btw: I have no memory leaks, thanks to valgrind.

• When does the competition finish? I think it's most ethical to submit your own work if there's a prize involved. May 23 '18 at 10:13
• @TobySpeight it ends tonight. I am currently number two. The price is getting 1 bonus on your final grade. May 23 '18 at 10:17
• If you can write an iterative version of Merge, it will likely be much faster. My version sorts a doubly linked list of 10 million random integers in less than 7 seconds on my machine. It sorted a doubly linked list of 10 million variable-length strings in about 16 seconds. Keep in mind that 10 million is 80 times 125,000. The code is much more complicated, however. Be prepared to draw a lot of pictures, and you will have to consider all possible cases (e.g. all the nodes in the left sublist merged first, all the nodes in the right sublist merged first, etc.). May 23 '18 at 12:23
• Can you add a link to your data set so we can do timings and compare? May 23 '18 at 17:21

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<std::string> 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<typename T>
T* Merge(T* firstNode, T* secondNode)
{
if (!firstNode) return secondNode;
else if (!secondNode) return firstNode;

else if (firstNode->getText() >= secondNode->getText())
{
firstNode->setPrev(Merge(firstNode->getPrev(), secondNode));
return firstNode;
}
else
{
secondNode->setPrev(Merge(firstNode, secondNode->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<typename T>
T* Split(T* my_node)
{
if (!my_node || !my_node->getPrev()) return NULL;
T* secondNode = my_node->getPrev();
my_node->setPrev(secondNode->getPrev());
secondNode->setPrev(Split(secondNode->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<typename T>
T* MergeSort(T* my_node)
{
if (!my_node) return NULL;
else if (!my_node->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;

{
}
// save sorted data into a new file called sorted.bin

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)
{
}


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->setPrev(temp);
return;
}
else if (prevKey)
{
return;
}
prevKey = new Key();
prevKey->setText(word.substr(0, 2));
prevKey->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.

• Thank you for this amazing feedback! I'm happy to hear that I'm doing things good and I also like the fact that I'm learning something new. I don't know exactly what unique_ptr is, but if it's something like smartpointers, we can't use it. I'm still a second year student. They don't allow us to use some easy things. As for the mergesort, I will look into it and redesign it. Let's say you have the word: Hello. The Key of Hello would be "He". Each key has another linkedlist with all the values in it. So all the words. In this case: Hello. I made the std::strings const references. Thankyou May 23 '18 at 14:31
• Look through The Standard Guidelines. If you are being forced to learn to write bad code, there is something wrong. I can see not using algorithms and containers when learning how to write fundamental data structures, but that does not preclude the entire standard library. May 23 '18 at 14:43
• I think I understand about the two-levels of linked lists. So the second call to sort I was asking about is the sorting of the specific sublist. Is that part of the problem, or your approach to dividing up the work for sorting? What textbook are you using? May 23 '18 at 14:45

Get rid of the recursion. Transform all into loops. Look up "bottom-up mergesort", where you start by merging single nodes into sorted pairs, then merging the sorted pairs into sorted quadruples, then merging those, continuing until you're left with one -- now sorted -- list.

Using one extra head node in front of the whole list will greatly simplify your coding. For an example, see Wikipedia for "tail recursion modulo cons".

• Welcome to Code Review! Whilst this may theoretically answer the question, it would be preferable to include the essential parts of the answer here, and provide the link for reference. May 23 '18 at 13:46
• Welcome to Code Review! You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and why it is better than the original) so that the author and other readers can learn from your thought process. May 23 '18 at 13:46
• what can I do, the whole code is based on that very thing that causes it to be slow - the recursive organization of the algorithm. the OP asks for the reason, and ways to increase the speed; so that's what I offered here. the only thing left is to write the new code. I can see no point in reviewing the particulars of the old code if it needs to be re-written wholesale. May 23 '18 at 16:18
• and that's fine, but you don't include of that information the answer; you just throw out some things they should do without any justification. If you include that information in the answer then it would be a much stronger answer May 23 '18 at 18:39