Sorting algorithms: JavaScript - Merge Sort 🚀
Tags: javascript, webdev, programming, algorithms
Published: 2021-02-07 11:39:24

Table Of Contents
        * 🤓 [INTRODUCTION](#intro)
        * 👉🏻 [ABOUT MERGE SORT ALGORITHM](#merge)
        * 👨🏻‍🏫 [EXPLANATION](#explain)
        * 👀 [VISUAL EXAMPLE](#visual)
        * 🛠 [IMPLEMENTATION](#implement)
        * 👩🏻‍💻 [CODE](#code)
        * 🤔 [COMPLEXITY](#complex)
        * 🙏 [THANK YOU](#thank-you)


## 🤓 INTRODUCTION <a name="intro"></a>

Welcome, hackers! I hope you are all having a great weekend.🚀Before we start another work week tomorrow, let's learn something new. In this blog article, we are going to explain and implement the Merge Sort algorithm.


## 👉🏻 ABOUT MERGE SORT ALGORITHM <a name="merge"></a>

Merge sort algorithm is another divide-and-conquer algorithm based on the idea of breaking down a list into several sub-lists until each sublist consists of a single element and merging those sublists in a manner that results in a sorted list.

Let's take a generic array that starts at index p and going through index r. It will be convenient to have a notation for a subarray, array[p..r]; In terms of our notation, for an array of n elements, we can say that the original problem is to sort an array A[0..n-1];


## 👨🏻‍🏫 EXPLANATION <a name="explain"></a>
Here is how merge sort uses divide-and-conquer:

**Divide** - by finding the number q of the position midway between p and r. Do this step the same way we found the midpoint in binary search: add p and r, divide by 2, and round down.

**Conquer** - by recursively sorting the subarray in each of the two subproblems created by the divide step. That is, recursively sort the subarray array[p..q] and recursively sort the subarray array[q+1..r];

**Combine** - by merging the two sorted subarrays back into the single sorted subarray array[p..r];


## 👀 VISUAL EXAMPLE <a name="visual"></a>
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/kywm45m0riiq1z55cwzq.png)

###Steps:
0: Array [14, 7, 3, 12, 9, 11, 6, 2] is unsorted
1: Find q (q = (p+r)/2) q=3 in our case
2: We divide into two subarrays [14, 7, 3, 12] - up to the index of q - And [9, 11, 6, 2]
3: Find q again in this case for each of the subarray
   The first subarray q index is 1 and for the second q=5
4: We divide into the following subarrays:
   [14, 7] and [3, 12] for the first subarray and [9, 11] and 
   [6,2] for the second subarray.
...Repeating these steps until we have only single values as an array member. We have to make two recursive calls in the conquer step.


##🛠 IMPLEMENTATION<a name="implement"></a>
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/9eugb2kvg6l3ci4u484f.png)


##👨🏻‍💻 CODE <a name="code"></a>
Play with the code!
{% jsfiddle https://jsfiddle.net/codespresso/tmzpqux1/10/ js,result,html,css %}


##🤔 COMPLEXITY <a name="complex"></a>
The complexity of the Merge sort algorithm is in the very best case Big O of nlog<sub>2</sub>n, in the worst case, the merge sort is staying consistent with the complexity of Big O of nlog<sub>2</sub>n.
The **bad** thing about the Merge sort algorithm is that requires an extra memory space the same size as the vector that is being sorted.


# 🙏 THANK YOU FOR READING!<a name="thank-you"></a>
References:
School notes...
School books...
[Khan Academy](https://www.khanacademy.org/computing/computer-science/algorithms/quick-sort/a/overview-of-quicksort)

Please leave a comment, tell me about you, about your work, comment your thoughts, connect with me! 

☕ SUPPORT ME AND KEEP ME FOCUSED!
<a href='https://ko-fi.com/Z8Z33D1HJ' target='_blank'><img height='36' style='border:0px;height:36px;' src='https://cdn.ko-fi.com/cdn/kofi4.png?v=2' border='0' alt='Buy Me a Coffee at ko-fi.com' /></a>

Have a nice time hacking! 😊