# Merge Ahead

Merge Sort in JavaScript.

As I continue my deep dive into data structures and algorithms the realization of the importance of sorting algorithms becomes more clear. A sorting algorithm arranges the elements in a collection of data in the correct order. One of the most useful sorting algorithms used is Merge Sort.

# What is Merge Sort?

Merge sort uses the concept of divide and conquer* *to sort a list of elements. This means it will divide one big problem into multiple smaller problems and then solve each of the small problems in order to solve the original bigger problem. Merge Sort is broken down into basically three steps:

- divide the given array into halves until we have an array that has one element or an array that is completely empty.
- once we have a smaller sorted array, merge those arrays back together until you’re back to the full length of the array.
- finally, once the array has been merged together, return the merged array.

*Here is a visual example of how Merge Sort works:*

`Example array : [3,4,2,1]`

- First, divide the array into smaller arrays until we can no longer divide the arrays any smaller.

` leftArray rightArray`

[3 , 4] [2, 1]

[3] [4] [2] [1]

- We need to merge the smaller arrays to get to the sorted array. When we compare
`3`

and`4`

they have already been sorted so we move on to`2`

and`1`

where`2 greater than 1`

so put`1`

first and`2 second`

.

` leftArray rightArray`

[3 , 4] [ 2, 1 ]

[3] [4] [2] [1]

[3, 4] [1 ,2]

- Now, compare the
`leftArray`

index of`0`

and the`rightArray`

index of`0`

which are`3`

and`1,`

`1`

is smaller than`3`

so that we removed`1`

from the`rightArray`

part and push into the`sorted array`

.

` leftArray rightArray`

[3 , 4] [1, 2]

[3] [4] [2] [1]

[3, 4] [2]

sorted array [ 1 ]

- Once again we check
`3`

and`2`

and removed`2`

from the`rightArray`

part and push into the`sorted array.`

` leftArray rightArray`

[ 3 , 4 ] [ 1, 2 ]

[3] [4] [2] [1]

[3, 4] [ ]

sorted array [1,2]

- Lastly, we need to merge the
`leftArray`

and`rightArray`

with the`sorted array.`

` leftArray rightArray`

[3 , 4] [1, 2]

[3] [4] [2] [1]

[3, 4] [ ]

sorted array [ 1 ,2 ,3, 4]

# How all that ⬆️ is written using Merge Sort!

array : [3,4,2,1]

function mergedSort(array,half = array.length/2){

if(array.length < 2){

return array

// it means we no longer divide the array into a smaller array

const leftArray = array.splice( 0,half );//left part of the array

return mergedArray( mergedSort( left ),mergedSort( array ) )

}

function mergedArray(leftArray, rightArray) {

const array = [];

while (leftArray.length && rightArray.length) {

if (leftArray[ 0 ] < rightArray[ 0 ]) {

array.push( leftArray.shift( ) )// remove from the left partand push into the sorted array

} else {

array.push( rightArray.shift( ) )// remove from the right part and push into the sorted array

}

}

return [ ...array, ...left, ...right ];

}console.log(mergedSort([3,4,2,1]));

//Output =>[1,2,3,4]

Hope this helps, Merge Away!