JavaScript Sorting Algorithms: Merge Sort
Tags: algorithms, javascript, sort
Published: 2021-02-16 21:27:10

<!-- wp:paragraph -->
<p>We are done with the basic sorting algorithms! Bubble Sort, Selection Sort and Insertion Sort were (I hope) easy to understand and wrap your head around. Implementing them will come <em>naturally</em> with time. Truth be told, those basic algorithms have their drawbacks - they do not scale well! <br><strong>Doubling</strong> the size of the input will <strong>double</strong> the time to produce the sorted array!</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>Thus, we will move to some more advanced algorithms, whose sorting time will be <em>O(nlog(n)</em>). Without further ado let us introduce the first of those efficient Javascript Sorting algorithms - <span style="text-decoration: underline;">Merge Sort</span>.</p>
<!-- /wp:paragraph -->

# Introduction to Merge Sort

<!-- wp:paragraph -->
<p>Merge Sort is quite different compared to the sorting algorithms we've seen. Merge sort divides the starting array into smaller arrays of 0 or 1 elements and then merges them back together. No need to loop through the array two times!</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>The whole process has two major steps:</p>
<!-- /wp:paragraph -->

<!-- wp:list -->
<ul><li>Dividing the array</li><li>Merging the smaller arrays back together</li></ul>
<!-- /wp:list -->

# Visualization
The Inputs for this algorithm are: `[38, 1, 40, 34, 9, 41, 2, 16]`. :bar_chart:

![Merge Sort Visualization](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zp2e89j1u94w8l6dy3jl.gif)
<figcaption>Merge sort visualization using visualgo. Please visit https://visualgo.net/ for more visual algorithms.</figcaption>
<br >
<br >
Seems like quite a lot of work right? But it is not, are just dividing the array (colored elements) and then merging the elements back together. Let us first understand the merging logic. At one point in the algorithm we had to merge the following subarrays - `[[1, 38], [34, 40]]`. Both of those are sorted - which is a requirement in order to produce a new sorted array that will contain all the elements found in those two subarrays.

# Merge Implementation

<!-- wp:paragraph -->
<p>This is the pseudocode for merge sort:</p>
<!-- /wp:paragraph -->

<!-- wp:list {"ordered":true} -->
<ol><li>Create an empty array and create indices <span class="has-inline-color has-nv-c-2-color">i</span> and <span class="has-inline-color has-nv-c-2-color">j</span></li><li>While there are still values that we haven't looked at<br>1. If the value in the first array is smaller than the value in the second array, we will push that value onto our empty array, increase the value of <span class="has-inline-color has-nv-c-2-color">i</span>, and move on to the next value in the first array<br>2. Otherwise, if the value in the second array is smaller than the value in the first array, we will push that value onto our empty array, increse the value of <span class="has-inline-color has-nv-c-2-color">j</span>, and move on to the next value in the second array</li><li>When all elements from one array are pushed to the sorted array, we will push all the remaining elements from the second array to the sorted array too</li></ol>
<!-- /wp:list -->


```javascript
function merge(arr1, arr2) {
  let results = [];

  let i = 0;
  let j = 0;

  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] <= arr2[j]) {
      results.push(arr1[i]);
      i++;
    } else {
      results.push(arr2[j]);
      j++;
    }
  }

  while (i < arr1.length) {
    results.push(arr1[i]);
    i++;
  }

  while (j < arr2.length) {
    results.push(arr2[j]);
    j++;
  }
  console.log(results);
  return results;
}
```
<br>
<br>

<!-- wp:paragraph -->
<p>Let us go through the code to see what is happening here, taking inputs <em><span class="has-inline-color has-nv-c-2-color">[[1, 38], [34, 40]]</span></em> as an example. We have created our empty array and our two indices before running the loop. The loop checks for the values of our indices i and j and whether they are less than the lengths of the two arrays we want to merge. If the element at the index <em><span class="has-inline-color has-nv-c-2-color">i</span></em> of <em><span class="has-inline-color has-nv-c-2-color">arr1</span></em> is smaller than the element of the index <span class="has-inline-color has-nv-c-2-color">j</span> of <em><span class="has-inline-color has-nv-c-2-color">arr2</span></em> we push that element onto our results array. </p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p><em>Taking into account our exemplary array we compare values at indices 0 and 0, which are 1 and 34, so we push 1 to the <span class="has-inline-color has-nv-c-2-color">results</span> array and increase the value of <span class="has-inline-color has-nv-c-2-color">i</span>. The next iteration we compare indices at 1 and 0, which are now 38 and 34, and considering 34 is smaller than 38 we push 34 to the <span class="has-inline-color has-nv-c-2-color">results</span> array (which is now <span class="has-inline-color has-nv-c-2-color">[1, 34]</span>), and we increase the value of <span class="has-inline-color has-nv-c-2-color">j</span>. We keep repeating this until we have the finished array, which will be sorted in the end.</em></p>
<!-- /wp:paragraph -->

# Merge Sort Implementation

*Keep in mind: this solution uses [recursion](https://javascript.info/recursion). Programmers who never worked with recursive code before might find recursion unintuitive, and it might be a good idea to check the link to understand the concept more.*


<!-- wp:paragraph -->
<p>Pseudocode for merge sort is as following: </p>
<!-- /wp:paragraph -->

<!-- wp:list {"ordered":true} -->
<ol><li>The algorithm will continue halving the array until it produces arrays containing no elements or only one element</li><li>Once those arrays exist the algorithm will merge back those arrays (using the method above) until the 'merged' array has the same length as the starting array</li></ol>
<!-- /wp:list -->

```javascript
function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  } else {
    let mid = Math.floor(arr.length / 2);
    let left = mergeSort(arr.slice(0, mid));
    let right = mergeSort(arr.slice(mid));
    return merge(left, right);
  }
}
```

<!-- wp:paragraph -->
<p>The base says that as soon as the length of the array is one or zero, we return the array, otherwise, we crate the middle element, and then divide the array into two subarrays <em>left</em>, and <em>right</em>, in the end, we call merge on those two arrays.</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>Now we look back at the visualization.</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>Conveniently, we have 8 elements in our array. The algorithm first divides the array into 4, then into 2, and then into one element sub-arrays. At one point the elements are all different colors - it means that they are individual. The algorithm then starts merging the elements back together - 38 and 1 become <em><span class="has-inline-color has-nv-c-2-color">[1, 38]</span></em>,   40 and 34 become <em><span class="has-inline-color has-nv-c-2-color">[34, 40]</span>, </em>and then these two arrays are combined-merged, and the algorithm runs until all the elements are sorted.</p>
<!-- /wp:paragraph -->

# Big O Complexity

<!-- wp:paragraph -->
<p>The best case, average case, and worst case of Merge sort are all the same - <em>O(nlog(n)</em>).<em> Log(n)</em> comes from the number of divisions the algorithm has to make. Having 8 elements means we would need to halve the array three times.</p>
<!-- /wp:paragraph -->

<!-- wp:list -->
<ul><li>First time we would get two arrays with 4 elements each</li><li>Second time we would get four arrays with 2 elements each</li><li>Third time we would get eight arrays with one element each</li></ul>
<!-- /wp:list -->

<!-- wp:paragraph -->
<p>If we would double the size of the input array, we would need to add one division to the algorithm! The n in the formula comes from the number of comparisons done when the arrays are merged back together.</p>
<!-- /wp:paragraph -->

# Conclusion
And that is our fourth JavaScript Sorting Algorithm article, with Merge Sort! A tiny bit more comprehensive than the basic three, but still pretty easy to understand, right?!  If you liked this one please check the whole series or visit my [blog](https://thedukh.com/) for more tech articles.