Introduction
Let´s talk about Merge Sort. We have many sorting algorithms for sorting our data and for most programming languages we already have built-in functions for sorting. So why we should bother us to learn things like Merge Sort or other sorting algorithms?
The answer is quite simple. It´s effective! Especially Merge Sort. And if you aim to work for FAANG companies (Facebook, Apple, Amazon, Netflix and Google) you have to know what Merge sort is and how it works.
First of all i need to say that merge sort is not that easy and to implement one from scratch is quite difficult if you just about to learn it.
The purpose of this article is to introduce you to merge sort and explain to you how it works. At the end of this article i will link you some great resources where you can dive deeper into the topic if you want.
Lets get started!
How merge sort works?
Merge Sort uses the "divide and conquer" approach. This just means that we divide for example an Array into half. Then we divide these arrays into half etc. until its not divisible anymore.
Then you compare those units and take the smaller number first and push it to a new array. We compare these smaller arrays and combine them while we sort them.
These steps repeat till we sorted the left and the right half of the array and then merge those two halfs to one.
For that we can use recursion as you will see in the example later on.
I could go into detail now and write about 3 sides about the theorie. But this would blow up this article. Like i said above i want to introduce you to this sorting algorithm. If you want to dive deeper into it you can use the resource section.
So lets dive into some code!
Javascript Example
I do not expect that you understand the code right away. I highly encourage you to take this code and play around with it to understand how it works. Break it, fix it, do anything you need to understand it. We learn through mistakes!
Big O
Like i said at the beginning merge sort is super effective. It has a time complexity of O(n log n). If you compare it to other sorting algorithms like bubble sort O(n²) it scales much better!
The downside is that you have a higher space complexity O(n). I think in our world time is more valuable than space and our computers these days have more than enough space so its worth it in my opinion.
Reference: https://www.bigocheatsheet.com/
Great Resources
Andrei Neagoie: https://www.udemy.com/course/master-the-coding-interview-data-structures-algorithms/
A great teacher (the best i known) where i got the code you see above. I can highly recommend this and any other course from him!
CS50: https://www.youtube.com/watch?v=Ns7tGNbtvV4
Great explanation!
Summary
I hope you enjoyed the reading and that you now have an idea on how merge sort works and why its so good. Feel free to drop comments if you have questions or find a mistake. I love to develop myself each day and whats better for improving than mistakes? :)
I wish you a nice day and stay safe.
Top comments (0)