What is Merge Sort in One Sentence?

Merge Sort is a computer science sorting algorithm, which essentially means that it takes a bunch of numbers and puts them in order.

What is an Example of Merge Sort?

We’ll start with a worked example to illustrate what merge sort is all about.

Let’s say that I have 4 numbers.

My numbers are (1, 41, 5, 0)

I want to sort these numbers out, so that they’re in increasing order.

In Merge Sort, I take my numbers and I give half of them to my friends, Bob and John.

So now, Bob has (1, 41) and John has (5, 0).

And now, Bob asks himself: “Is 1 less than 41?”

It is!

So, 1 comes before 41.

Therefore, Bob’s numbers have been sorted: (1, 41).

Now, it’s John’s turn.

Does 5 come before 0? No! 0 comes before 5.

So, John re-orders his numbers.

Merge Sort – Returning Numbers Back

And now, they both give their numbers back to Kushal.

And now, Kushal has to “merge” the (1, 41) and (0, 5) into a new sorted list.

So, he points to the first item in both lists.

Between the 1 and 0, what comes first? The 0 comes first. So, we add it to the list of sorted numbers.

And now, we increment the arrow pointing to the 0.

So now, the right arrow points to 5.

And we repeat. Between 1 and 5, 1 comes first. Add 1 to the sorted list and increment the arrow that points to 1.

Now, between 41 and 5, 5 comes first. Add 5 to the list and increment the arrow.

At this point, length of our sorted numbers is one less than the length of our unsorted numbers. This means that we have 1 more number to sort.

And that is our last number, 41.

There you have it! Merge sort, clearly explained.

If you’re a new computer science student, or are thinking about getting into computer science, check out my advice for new computer science students.

Thanks for reading! If this helped you, make sure to subscribe to Kushal Writes for more awesome computer science concepts to level up your programming skills.