Easy complexity analysis of Merge Sort

Photo by pine watt on Unsplash

Hi folks,

You’ve been told that the time complexity of Merge Sort is nlogn, and if you are like me you’re wondering why.

In this article I’m gonna guide you to a complete understanding of nlogn complexity in relation to Merge Sort.

Simplest idea of logarithm

You may know from school that logarithms have bases,
but in time complexity analysis the base is always 2.

I don’t want to scare you with math concepts,
infact I’ll rather give a sense of what logn is with an example.

You can think logn as a series of subsequent halving.

Suppose we have a sweet cake,
that someone has cut into 4 slices.
eat half of it,
eat half of the remaining (not the other half!),
leave a piece to your dear mom!

Now count the number of steps it took you to arrive to a single piece.
Just 2 steps, isn’t it?
Okay, that number is exactly the logarithm of 4 slices of cake.

Now imagine that in place of the cake there’s an array, and instead of you there’s an hungry computer…
Imagined?
Okay, now let the computer consume half of the array,
then half of the remaining,
and so on…
When there’s just one element left count how many steps it took.
I think you got the idea!

It carries out that: the logarithm tells you how many steps it takes the process of subsequently halving something.

First piece of puzzle: MERGING

Merge Sort is named like that because it works by merging two ordered arrays (it does so by using a two pointers tecnique).

Let’s look this pseudo-code

This piece of code takes linear time, infact it will do as much operations as the number of elements in the longest array.

This is the first piece of the puzzle:
the first n in nlogn.

Second piece of puzzle: HALVING

For those few that are still here I’m about to show where the logn in nlogn comes from!

Let’s look this GIF

Merge Sort in action

As you see the array is subsequently halved until its single items.

Merge Sort is a combination between
the halving process in the GIF
and the pseudo-code function previously shown.

It works because when there are only single item arrays (bottom of GIF) those are guaranteed to be already sorted!

Merge-sort them in pair,
walk back the entire structure,
until you have your full array back,
and that’s sorted!

Remainder: the logarithm tells you how many steps it takes the process of subsequently halving something.

So basically you are applying that pseudo-code function which takes n as time complexity, logn times.

Bonus: Merge Sort (recursive and iterative)

Fin

I hope you‘ve found useful information here.
If so leave a thumb up below and don’t forget to subscribe!