what I learned last week: merge sort algorithm
Tags: javascript, algorithms
Published: 2022-03-07 21:38:42

I know it's been several weeks since I last posted an entry but I'm happy to be back after successfully completing General Assembly's Java Immersive Program! 

<img width="100%" style="width:100%" src="https://media.giphy.com/media/l0amJzVHIAfl7jMDos/giphy.gif">

Prerequisite: [Recursion](https://www.geeksforgeeks.org/recursion/)

Lets get right to it. In this entry I'm going to go over Merge Sort which is a [Divide and Conquer](https://www.geeksforgeeks.org/divide-and-conquer-algorithm-introduction/) algorithm.

![merge sort example](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/g39i4e9bwgv1hdqckmig.png)

Remember, the divide and conquer technique can be divided into three parts:

1. Divide: This involves dividing the problem into smaller sub-problems.
2. Conquer: Solve sub-problems by calling recursively until solved.
3. Combine: Combine the sub-problems to get the final solution of the whole problem.

So, let's say you are asked to sort the unordered array below.

![unordered array](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1gtlmupq7scpfhtrinxj.jpg)

How would you achieve this and return this ordered array? One way, would be utilizing Merge Sort.

![ordered array](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/qexjwx321p60w510go4d.jpg)

The first thing, we want to do is divide the unordered array into halves.

![step 1](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ijq0uoak57q12g3wbqlr.jpg)

Next, I divide these two arrays into halves.
![step 2](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/uds9zupazg3ajbi5bzp0.jpg)

We further divide these arrays until we reach [atomic value](https://www.ibm.com/docs/en/db2/11.5?topic=model-atomic-values) and the array can no longer be divided . 
![step 3](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3o79v2h6ebnx70uv34c4.jpg)

Now, I will combine them in a sorted manner. 
![step 4](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/eyx2izr716knu5f0tkhs.jpg)

Next, I continue combining the arrays in a sorted fashion. 
 
![step 5](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/yu74kw0zwnd7rfriwl5p.jpg)

The final merge will look like this.
![step 6](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/znpmnju4iti5i9jrgjxy.jpg)

You're probably asking yourself "how do I code the above algorithm?" First step, we need to write some pseudocode. 

In computer science, [pseudocode](https://en.wikipedia.org/wiki/Pseudocode) is a plain language description of the steps in an algorithm or another system. Pseudocode often uses structural conventions of a normal programming language, but is intended for human reading rather than machine reading. 
```
Example Pseudocode

//array of elements
let arr = []

mergeSort(arr) {

//variable that stores number of elements in the array
n <-- array.length 

//cut the array into two halves
if(n < 2) {
    return n
  }

mid <-- n/2
left <-- array of size(mid)
right <-- array of size(n-mid)

for(i <- 0 to mid - 1) {
    left[i] <- arr[i]
  }

for(i <- mid to n - 1) {
    right[i - mid] <-- arr[i]
  }

//recursion
mergeSort(left)
mergeSort(right)
Merge(left, right, arr)
}
```
[Justin Kim](https://www.youtube.com/watch?v=x_Z9FcAPmbk)
```
Code Implementation in JavaScript

//helper method
const merge = (leftArr, rightArr) => {
    const output = [];
    let leftIndex = 0;
    let rightIndex = 0;

    while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
        const leftEl = leftArr[leftIndex];
        const rightEl = rightArr[rightIndex];

        if (leftEl < rightEl) {
            output.push(leftEl);
            leftIndex++;
        } else {
            output.push(rightEl);
            rightIndex++;
        }
    }
    return [...output, ...leftArr.slice(leftIndex), ...rightArr.slice(rightIndex)];
};

//console.log(merge([3, 6], [2, 4]));

//recursive function
const mergeSort = arr => {
    if (arr.length <= 1) {
        return arr;
    }

    const middleIndex = Math.floor(arr.length / 2);
    const leftArr = arr.slice(0, middleIndex);
    const rightArr = arr.slice(middleIndex);

    return merge(
        mergeSort(leftArr),
        mergeSort(rightArr)
    );
};


console.log(mergeSort([1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92]));
```
Now if you run the program, you will see a newly sorted array
```
$ node app.js
[
    1,    1,   2,   2,   4,
    8,   32,  43,  43,  55,
   63,   92, 123, 123, 234,
  345, 5643
]
```
In conclusion, here is a group of folk dancers explaining Merge Sort. Yes, you read that right. 

{% youtube XaqR3G_NVoo %}

resources
https://www.tutorialspoint.com/data_structures_algorithms/merge_sort_algorithm.html
https://www.youtube.com/watch?v=TzeBrDU-JaY&t=69s
https://www.youtube.com/watch?v=x_Z9FcAPmbk