Shares

Learn the Merge Sort Algorithm with Clarity and Detail

In this tutorial, we will be breaking down the merge sort algorithm. We will scrutinize it until you are sick of even hearing the word merge sort. Give you dreams, visions and even possibly nightmares about merge sort. Hahaha kidding.

With this single tutorial, I hope that crying about how difficult it is to implement merge sort becomes a thing of the past.

The merge sort algorithm is a divide and conquer sorting algorithm that has a time complexity of O (n log n). Therefore, it is an extremely versatile and reliable sorting algorithm. Surprisingly enough, it is also not that difficult to implement and understand. Don’t worry if you don’t know what kind of technique divide and conquer is. We will be going through that very soon.

By the end of this tutorial, you will feel like you can take on the whole world. Algorithms will seem like a piece of cake. Okay, maybe not all algorithms. But you will definitely gain some knowledge and we will make it stick to your brain. Like glue, or that stalker in high school who wouldn’t stop following you.

The source code is available in the following languages

• JavaScript,
• Java
• C++
• Python

Okay, enough chit chat, lets dive into the tutorial.

Merge Sort Algorithm Fun Facts

Before going into the actual contents, I would like to present some fun facts

1. Merge sort is a stable sort. In another words, if two values are equal, the relative order prior to sorting will be maintained.
2. The worst case time complexity of Merge sort is O (n log n).
3. The space complexity of merge sort is  O (n).
4. Merge sort scales well with large amounts of data.

Divide and Conquer Algorithms Simplified

In the introduction I mentioned the concept, but I did not explain what it meant. What is the first thought that pops into your mind when you hear the words “Divide and Conquer”?

War? Possibly some sort of war-based video game where you split your troops and conquer multiple cities?

Well, that is pretty much what divide and conquer is. Splitting up a big problem into smaller problems. Combine all the solutions to form the answer to the problem.

Going back to the war-based video game analogy, if the whole purpose of the game is to conquer the country, that would be the big problem. The smaller problem may be to conquer the smaller provinces. Lets say that there are 8 provinces. The goal of conquering the country can be split into smaller goals. In this example, 8 smaller goals of conquering each respective province. Combine all those small goals together and you have finally conquered the entire country.

Hopefully my analogy there made perfect sense. If you can’t tell I am a geek, so I use geeky examples to drive home certain points. To sum it up, in the context of programming, divide and conquer can be broken down into four specific steps.

1. Identify the base case. My recursion sensors are tingling.
2. Divide the problem: break it down into smaller, identical tasks. These smaller tasks are also known as sub-problems.
3. Conquer each sub-problem: Solve the smaller problems. This can be done by reducing the problem until it reaches the base case, which is the solution.
4. Combine the solutions to the sub-problems to get the answer.

For those who thought Divide and Conquer, as well as merge sort was difficult, NEWSFLASH. It ain’t rocket science.

Hopefully, divide and conquer algorithms make more sense now. We will be applying this concept to build our own merge sort algorithm.

Merge Sort Algorithm Overview Now that we have a general understanding of the behaviors and traits of the Divide and Conquer Algorithm, we can move onto looking at the merge sort algorithm.

First of all, divide and conquer should yell recursion. Why? Think about it for a moment.

Dividing a problem into smaller, identical tasks? Recognizing a base case? RECURSION ALERT!

Another point to keep in mind is that every recursive solution can be implemented iteratively. However, this will often come at the cost of readability.

We implement recursive approaches because they are much more readable. Recursive approaches come at a cost however. Each recursive function call is stored on the call stack, which results in a space complexity of O(n).

However, I prefer the recursive approach, because readability is often the number one priority of a developer who writes code.

Why? Because we write code not for the machine to interpret, but for the developer who comes after us to maintain the code. Otherwise, we would all be writing code in assembly for all those micro-optimizations right?

We have established the fact that Divide and conquer algorithms can be broken down into 4 major specific steps. Merge sort is no different.

Let us first identify the base case. In each divide and conquer algorithm, the base case should ultimately be the solution at the most lowest level possible.

Now, before proceeding to find out the answer, I want readers to grab a pen and paper. Spend 5-10 minutes jotting down the answer to the following question.s

1. What problem does the merge sort algorithm solve?
2. The base case presents a solution at the lowest possible level. What could be a possible base case for this algorithm.

Step #1 Identify the Base Case

I am going to keep the explanation as simple as possible. Before proceeding, readers should be familiar with recursive functions. Take some time to familiarize yourself with recursion.

Otherwise, although you may understand the theoretical aspects, when you start looking at the code, your head is going to be spinning and spinning like the swirling icon that you see on sites when it is loading.

Okay, assuming that everybody has an understanding of recursion: the base case is super simple.

Is a list containing a single element sorted?

NEWSFLASH: A list with only a single element, is of course … SORTED. Surprise of the century right? This is the base case.

Pseudo Code

So basically, the base case (pun intended) looks like the following in pseudo-code.

if length of list is less than two
return list

I am going to be constantly writing pseudo code as I write. The reason for this is so that you are being trained to read and express yourself through logic. A secondary reason is also to identify any potential pitfalls or flaws in our way of thinking.

As you write pseudo code, you will notice that your thoughts become much clearer. The reason for this is that writing down your thoughts is a way of processing and evaluating. Both are very important soft-skills that you will often rely on during your life as a programmer.

Step #2 Divide the Problem

Now that we understand that a list is “sorted” when it only has a single element, we can look towards dividing up the problem into common tasks.

Basically, we will need to split the list into halves until we can no longer split into halves. This will take O (log n) time complexity.

Suppose that we are dealing with the following list

[11, 28, 8, 15, 50, 20, 90];

Visually, the task of dividing up the problem until we reach a base case will look like the following. If you are wondering why the left list has one more element in the second row, it is just the way I will be implementing it. It doesn’t matter if the left list has length of 3 and the right list has length of 4. If you want, you can implement it so that the left list has length of 4 and right list, a length of 3. This is simply a stylistic choice.

The important point here is that on each iteration, we are dividing the list into halves.

Anyway, we are dividing the problem into smaller problems here. When we reach the base case (I.e. n lists of length one), we have sorted lists at the lowest level.

From then on wards (this is the conquering part), we work our way upwards and solve the smaller problems. Then we combine the smaller solutions to form the sorted list.

Hopefully this makes sense. Please leave a comment if it doesn’t and I will update this post and add more detail. Lets move onto the pseudo code for this logic.

Pseudo Code

Okay … its pseudo code time. In order for us to avoid an endless loop and reach the base case, the lengths of the list passed must be constantly decreasing.

Take a look at the diagram above. What is going on in each of the rows?

Step #3 Conquer Each Sub-problem

If sorting the list of 7 is conquering the entire country, think sorting an list of lengths 2 and 4 as conquering a city and a province respectively.

When reach the base case of having 7 lists, each containing a single element, we need to perform the following operation.

Task: Merge adjacent lists. This means we have a list on the left and a list on the right.

Step 1. Compare the first elements of both lists one by one.

Step 2. Move the smaller element out of the list it was found in. Add this value to the list of “sorted items”.

Step 3. Repeat the process.

Step 4. One list should still contain elements. This list is sorted. Move its contents into the result list.

Words might not be enough to convey the message, so let us examine another visual diagram. Case #1 Merging Lists with Single Element

First of all, we start of with lists with length property equal to one. I.e.

, , , , , , 

As you can see, in the second row above, we have four lists. The first three lists have length property of 2 and the last one, 90 (since we are sorting an list of length property of 7). Let’s walk through how this joining, stitch process (or whatever you want to call it) is done.

First of all we need to join adjacent lists together. When we join, we compare the item on the left with the right. If the item on the left is less than the item on the right, the positions don’t switch. However, if the item on the right is less than the item on the left, we make a switch. In the diagram above, if you examine 50 and 20 (the 3rd and 2nd last elements respectively), notice how the positions are switched? Before the merge 50 was before 20. It is because of the results of the comparison that the positions were switched.

Case #2 Merging lists With More than One Element

In case you are lost, we are now on row 2 containing the following elements:

[11, 28],  [8, 15], [20, 50], 

Wait a minute! Now we are dealing with two items in each list. How are we meant to perform the comparison now? Since things are going to get slightly more complicated, lets take a look at the list after the first merge. We need to combine the first and the second list – [11, 28] and [8, 15].

Lets take a look at what the pseudo code will look like.

compare the following lists
[11, 28]
[8, 15]

compare 11 and 8. 8 is less. Therefore, take 8 and put it into the new list
compare 15 and 11. 11 is less. Therefore, take 11 and put it into the new list
compare 15 and 28. 15 is less. Therefore, take 15 and put it into the new list
since right list is empty, put the remaining elements in the left list (  ) into the new list

Afterwards, we need to combine the third and the fourth list – [20, 50] and .

compare the following lists
[20, 50]


compare 20 and 90. 20 is less. Therefore, take 20 and put it into the new list
compare 50 and 90. 50 is less. Therefore, take 11 and put it into the new list

// Note that on each iteration, each list is sorted. Therefore, it is okay to
// plug the remaining items in any left over list at the end of the new list

since left list is empty, put the remaining elements in right list (  ) into the new list

The result after the the following merge sorts is the following lists. We have reduced four sorted lists into two. Repeat the Process Until Only a Single List is Left Remaining

Now, we are going to repeat this process until we are finally dealing with a single list. Yep, same thing over and over again. But lets go through it together anyway for the sake of completeness.

We will be working with the following items

compare the following lists
[8, 11, 15, 28]
[20, 50, 90]

compare 8 and 20. 8 is less. Therefore, take 8 and put it into the new list
compare 11 and 20. 11 is less. Therefore, take 11 and put it into the new list.
compare 15 and 20. 15 is less. Therefore, take 15 and put it into the new list.
compare 28 and 20. 20 is less. Therefore, take 20 and put it into the new list.
compare 28 and 50. 28 is less. Therefore, take 28 and put it into the new list.

// right list contains [50 and 90]. Because each list is sorted,
// we can just take all the elements and add them to the end of the new list
since second list is empty, put the remaining elements in the right list ( [50, 90] ) into the new list

Hopefully by now, all of this is making sense now. In order to have the readers critically assess the code and draw their own conclusion, up until now, I have not added a super detailed description of what is going on.

To make things clearer, here is a visual diagram of what is going on during the merging process. In case you still don’t fully understand what is going on, no shame. Merge sort is a hard algorithm to grasp at first. I will draw it out below for you. By the end of this tutorial though, you will be super confident with the merge sort algorithm. So hang in there!

Step 1. After comparing 8 and 20.

Result list: 

Left list: [11, 15, 28]

Right list: [20, 50, 80]

Step 2. After comparing 11 and 20.

Result list: [8, 11]

Left list: [15, 28]

Right list: [20, 50, 80]

Step 3. After comparing 15 and 20.

Result list: [8, 11, 15]

Left list: 

Right list: [20, 50, 80]

Step 4. After comparing 28 and 20.

Result list: [8, 11, 15, 20]

Left list: 

Right list: [50, 80]

Step 5. After comparing 28 and 50.

Result list: [8, 11, 15, 20, 28]

Left list: empty

Right list: [50, 80]

Step 6. Add whats left of the right or left list to the result list

Result list: [8, 11, 15, 20, 28, 50, 80]

Left list: empty

Right list: empty

MergeSort Algorithm Pseudo Code

Okay, now that we know what is going on, we can take a look at the pseudo code of the merging operation. We went through the entire operation together, so I will keep the explanation brief.

start mergeSort(leftList, rightList)

declare new result list to store result

for n elements in list
leftItem is first item in the left list
rightItem is first item in the left list

if leftItem is greater than rightItem
push rightItem into result list
remove rightItem from right list
otherwise
push leftItem into result list
remove leftItem from left list
end loop

while leftList has elements
push leftItem into result list
remove leftItem from left list
end loop

while rightList has elements
push rightItem into result list
remove rightItem from right list
end loop;

return result list

end mergeSort

In the for loop, what we are doing is quite obvious. We compare the first elements in the left and right list. we take whatever is smaller and we put it into the result list. Afterwards, we move it from the source (the source is either the right or the left list).

The loop will continue until either one of the lists (left or right) empties out. Logically speaking, both lists cannot empty out at the same time, so, one of the two subsequent loops will trigger.

The subsequent loop contains the logic for dumping the left over elements into the result list. Simple right?

Congratulations! You have mastered the merge sort algorithm! Now, we will just look at the final piece of the puzzle. Combining the sub-solutions to get the

Step #4 Combine the solutions to get the Answer – Examine the Call Stack

This might seem kind of obvious but bear with me. After we recursively build up our answer, once we reach the base case, each of the recursive function calls will be popped off the call stack.

In order to fully understand what is going on, it is best to examine the call stack. I will draw out exactly how the call stack looks like on each part.

Trust me, you will thank me later. If you really do get something out of this, or need clarification, please leave a comment. It is the only way I will know whether I have done my job properly.

Merge Sort Algorithm Pseudo Code

We already went through the pseudo code for the merge function. The pseudo code for the merge sort contains the big picture operation of the merge sort. Therefore, it should be simpler to understand. Read through the code first and afterwards, lets break down the pseudo code logic and look inside

mergeSort(list)
// Step #1
if list only has one item
return the list

// Prepare for step #2 and #3
left list is left half of list rounded up
right list is right half of list rounded down
// Step #2 and #3 --> divide and conquer!!!!
left list equals the result of mergeSorting left list
right list equals the result of mergeSorting right list
// #step 4
return the result of merge(leftList, rightList);

If the list has only item, we established that it is already sorted. Therefore, just simply return the list.

In the next line, we declare two variables and store the left half and right half of the current list. Why did I say current list? Care to take a guess? If not, don’t worry because you will soon find out.

In the next pair of instructions, we set the left and right list as the result of merge sorting the left and right list respectively. Here is where the recursion magic occurs.

Recommended Watch

If after reading through the article, you are still not 100% confident with the merge sort algorithm, I recommend watching the following video. I personally think this video is great at explaining the merge sort algorithm and its underlying logic.

Especially if you are a visual learner, take advantage of the visual demonstrations coupled with the solid explanations in this video. I have to admit that the video is extremely well made and the guy in the video does an extremely good job covering all the bases in such a short period of time.

Using cups and writing numbers on them. And then shuffling those around to explain sorts.

Why did I not think of that? Even as I am writing this post, I am amazed at the simplicity, but also the resourcefulness of such approach to teaching sorting algorithms.

I Understand the Theory But Have no idea how to code it

If this is your situation, chances are, you probably need to build up your fundamentals.Hard pill to swallow, but it will help you to grow and develop your skills.

If I were you, I would not neglect these fundamentals, because they are called fundamentals for a reason.

Whatever problem you come across, your fundamental knowledge is whats going to help you solve those problems and write out the code.

Some of the topics you should focus on are

• Recursion.
• Call by reference vs value.
• Conditional statements and basic operators.
• Arrays.
• Knowledge of other data structures will help as well.

Try solving algorithmic problems and code regularly. Eventually, you will be able to come up with your own solution in due time.

Also note that there are other small alternatives that you can add/tweak in the merge sort implementation. So feel free to get creative. Just make sure that your algorithm though doesn’t turn into another sorting algorithm though.

In the meanwhile, hang in there and keep on persevering!

Homework and Source code

What? You didn’t think I was going to let you get away without doing some homework did you? Nope … tsk tsk tsk!

Your homework, should you choose to accept is the following

Write the merge sort algorithm in your favorite language. And don’t cheat if you can. That defeats the purpose of the homework assignment.

Great, I am just going to whistle and assume that you will not check the answers until after you have finished/attempted the homework.

The source code is also available in the following languages

At this point, I am pretty confident that you have a solid understanding of the merge sort algorithm. Hope you enjoyed the read and that you got a lot out of it.

If you found the content in this post helpful, please share this post. Hopefully those who you share with will thank you for it.

Until next time, peace! And code with delight 🙂

About the Author Jay

I am a programmer currently living in Seoul, South Korea. I created this blog as an outlet to express what I know / have been learning in text form for retaining knowledge and also to hopefully help the wider community. I am passionate about data structures and algorithms. The back-end and databases is where my heart is at.