No, it’s not.

I should just get this! why don’t I get this!

That thought ran through my head a hundred times while I spent the last couple weeks or so trying to wrap my head around Merge Sort.

For context, I’m a developer with 2 years of Industry experience but I chose the Code Bootcamp route over University. I still have a long way to go and a lot to learn — but for some reason, I felt that with my experience I should pick up a “simple” sorting algorithm easily. I mean this is something that CS courses will teach within the first few weeks.

I’m sure I’m not the only person who’s been frustrated that they aren’t understanding something or learning something at the pace they expect.

I hope that by sharing what I learned, and the difficulty of that experience I can help other people who are stuck on Merge Sort or stuck on anything really!

Stop telling me it is

It’s easy!

Anytime I see this in a tutorial I take a pause to sigh. Please never ever do this if you’re teaching anything to anyone. Everything is hard until you understand it. Then it’s easy. Easy is relative — and telling people something is easy is a great way to make them feel stupid for not understanding.

Maybe it IS easy for you. If so, that’s awesome! But it wasn’t easy for me. Something else might be easy for me and hard for you, and that’s OK — such is life.

if only it were so simple…

“to merge sort: sort the left half of the array, sort the right half of the array, then merge and sort those together.”

…how?

In hindsight, every tutorial I read or watched made total sense. If you already knew what they were talking about. But, In many — or at least in the tutorials I encountered I would see some statement like that followed by a couple of hundred lines of code. Or a pretty picture with no relation to the actual code.

So how do you do it?

Merge Sortis broken down into two functions: Merge and Merge Sort. I’m going to break down their responsibilities at a higher level first, then go into the nitty-gritty implementation details after.

Merge

Merge takes an already sorted left half and already sorted right half of the original array.
Merge crawls over these arrays creating a resulting array from the smallest values until either the left or right array is empty.
lastly Merge pushes the remaining elements of the left or right array into the result.

Implementation using Javascript

I’m currently learning C but I’m primarily a Javascript developer. I found it really useful to see an implementation of MergeSort in Javascript because the language lets us skip a few hidden steps.

In the above, you may notice that in Javascript we can treat Merge Sort fairly similar to the high-level steps mentioned before.

Implementation using C

In C there are a few more steps to add. Primarily because we’re going to be mutating the original array rather than creating copies, and because we have to know the size of the arrays we’re using when we declare them.

Instead of creating the individual right and left arrays, we’re going to take the original array, start index, and end index as inputs to know which elements of our original we’re using Merge to sort

so imagine we wanted to Merge the array {4,5,1,2}. we could call merge({4,5,1,2}, 0, 3) and it should mutate the array into {1,2,4,5}

Note: forgive me for my Javascript background. I’m used to different variable naming patterns and legitimately didn’t notice until I started editing this post. Oops!

Merge Sort

Merge Sortis a recursive function (fancy word for a function that calls itself). its main goal is to Merge Sort the left half of an unsorted array, Merge Sort the right half of an unsorted array, then Merge those two together.

So using {3,2,4,8,5,7,6,1} as our example, we’re going to step through this code. the cool thing about recursion is that we’re calling Merge Sorton the left and right half of our array before we merge it. This means we start merging arrays with only 1 element together. then merge our arrays with 2 sorted elements together, then 4 sorted elements and so on.

Best of Luck!

Hopefully, that helps you figure out merge sort — or at least makes you feel better if you’re currently struggling to learn something *easy* just like I was.

I’ve only started writing recently and do it mostly for fun and to learn so please let me know if there’s anything you think I can do to improve!