Ksetyadi's [B]Log

First or second year of Computer Science’s students should not be surprised with this as this is one of the main subjects that must be mastered in order to advance to the next year. This subject usually taught in parallel with another algorithm in a lecture called “Introduction to Algorithm” or “Data Structures and Algorithm” depending on your campus.

It’s been years since I’ve got this material from university and I always come back to this subject again and again. Merge sort is one of the basic sorting algorithm but I still amazed with the way it do the sorting. So I set this weekend to visit the material again plus adding some more information about the merge sort into my head that once I’ve never known before (I’m not a nerd while back at the university so I don’t ‘eat’ everything my lecturer gave to me).

Let’s start with the easy one.

Merge Sort is a comparison-based sort

“What? So there are another sort methods that didn’t use comparison?”

Yes. (See here for one of the examples).

So what is comparison-based sort? The most intuitive way is to describe a comparison-based sort as a job to sort a bunch of weights using a balanced scale. You have, in example, 5 weights in different weight (or course, so we can sort it out, right?) but you don’t have any idea with how many weight exactly they are. So what you’re going to do? You start comparing those weights using balanced scale and mark which one is lighter and which one is heavier. You keep comparing until you’ve finished with all of them and, in return, resulting a sorted set of weights.

In a more abstract (ehem, mathematical) way, we can write this as a list or array of any integers. Let’s say we have the list k = [10, 5, 8, 2, 4, 9] and we want to sort them out. So we start comparing any numbers in it, for example 10 with 9, 5 with 8, 2 with 4, and so on. Doing this process over and over again will result a list of sorted integers s = [2, 4, 5, 8, 9, 10]. That is the comparison-based method. Let’s move on.

It is a stable sort

By definition, stable sort is the kind of sort that always maintain the relative orders of the thing you want to sort. Let’s say you have another set of integers a = [3, 7, 5, 9, 7, 10, 2, 1, 4, 5]. In the end, you’ve got the result b = [1, 2, 3, 4, 5, 5, 7, 7, 9, 10]. Let’s focus our eyes to the same ‘5’ and ‘7’ in the result. You’ve probably don’t really care which 5 or which 7 was that but the stable sort cares. The first ‘5’ in b was the ‘5’ in a = [3, 7, 5, 9, ...] and the second ‘5’ in b was the ‘5’ in a = [..., 2, 1, 4, 5].

Now let’s move to the most interesting part: the algorithm itself.

Merge Sort Algorithm

Earlier today, I’ve challenged myself to finish merge sort code written in Python in just a few minutes (max. 10 minutes). As you might know, Merge Sort use the divide-and-conquer algorithm to solve the problem. It’s pretty straightforward and the concept is relatively easy to be remembered. But since this will be a long post if I added the algorithm here, I will write about that in the next post.

Now go to sleep. It’s already 2AM.