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.

Get Ready to Merge!

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:

1. divide the given array into halves until we have an array that has one element or an array that is completely empty.
2. once we have a smaller sorted array, merge those arrays back together until you’re back to the full length of the array.
3. 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 therightArray 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!