Sorting Algorithms: Merge Sort
Published: 2021-04-07 18:53:51

On today's series of __Sorting Algorithms__, I will be getting down with the __Merge Sort Algorithm__!

### What Is A Merge Sort Algorithm?
Merge Sort is described as a _divide and conquer_ algorithm. What this means is, we start off with an array of items, we must divide that array in half. Now that we have two arrays, we start comparing each element to the opposing array. Whichever is smallest, must go into the empty array. As a result, we return a new sorted array.

{% youtube KF2j-9iSf4Q %}
***
Now, before we get into the code, like the algorithm itself, we must break down how to implement _merge sort_ in two functions!
***
# Merge a Nearly Sorted array
In this function, we will be taking our array, splitting it down the middle, giving us two arrays. With recursion, we will keep splitting those two arrays until they are an array containing one element  

## The PseudoCode
- Break up the array into halves until you have arrays that are empty or have be an element.
- Once you have small & sorted arrays, merge those arrays with each other until they are back at full length.

### The Code
```javascript 
//helper method to sort the array
const mergeSort = (arr) =>{
  //base case if our array length is too small.
  if(arr.lenght <= 1) return arr 

  //first split the array in half
  let mid = Math.floor(arr.length / 2)
  //assign the left half of the array from beginning to middle
  let left = mergeSort(arr.slice(0, mid))
  //assign the right half of the array from mid to end of array
  let right = mergeSort(arr.slice(mid))
  //return sorted array by calling merge function to merge the now sorted pieces together
  return mergeSort(left, right)
}
```
***

# Merging Arrays
How we can approach this function is, with our two split up arrays from our __mergeSort__ function, we will now start comparing if an element is the smallest in the left or right array, that element will get pushed into our results array.

## The Pseudocode
- Create an empty array, look at the smallest values in each array
- while there are still values we haven't looked at, 
- __if the value in the first array is smaller than the second array, push that value into the results and move to the next element in the first array.__
- This same logic goes for the second array, if the value there is smallest, push that to the results array. 
- Once we exhaust one array, push the remains from the other to the results array and return.

### The Code
```javascript

//create the merge function, it takes in two arrays 
const merge = (arr1, arr2) =>{
  //create a reults array to return merge srted array
  let results = []
  //assign i and j to 0 as comparison pointers 
  let i = 0, j = 0
  //create a while loop going through both arr1 & arr2 loping at each index
  // while there are still elements in our arrays, do this
  while(i < arr1.length && j < arr2.length){
    //ask if arr1[i] is less that arr2[j]
    if(arr1[i] < arr2[j]){
      //if arr1[i] is smaller, push that number in our results array
      results.push(arr1[i])
      //move to the next value in arr1
      i++
    } else {
      //if arr2[j] is smallest instead push that to our array
      results.push(arr2[j])
    }
  }
  //since there is a possibility of remaining elements in either of the arrays we must lop through them again while they are not empty
  //while there are still elements in arr1, iterate through them and push them to results array, these remaining elements will already be sorted because of merge helper function
  while(i < arr1.length){
    results.push(arr1[i])
    i++
  }
   //while there are still elements in arr2, iterate through them and push them to results array, these remaining elements will already be sorted becasue of merge helper funtion
  while(j < arr2.length){
    results.push(arr2)
    j++
  }
  return results
}
```
### Without Comments

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

  let i = 0
  let j = 0

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

  return results
}


function merge(arr){
  if(arr.length <= 1) return arr

  let middle = Math.floor(arr.lenght / 2)
  let left = mergeSort(arr.slice(0, middle))
  let right = mergeSort(arr.slice(middle))
  return merge(left, right)
}
```
***

### Time and Space Complexity
- The time complexity of a merge sort algorithm at best, average, and worst case is O(n log n). 
- The space complexity of this algorithm is O(n).
***

## The Conclusion
The Merge Sort Algorithm is highly more effective than implementing Bubble Sort or Selection Sort. It simply breaks down the array only to build it back up again. Now that w are diving into the more advanced sorting algorithms, I will be talking about Quicksort and the advantages it has in sorting! 

Until Next time!
Happy Coding :)