Dec 4, 2022 Author - Sai gowtham

How implement merge sort algorithm in JavaScript

algorithms3min read

Merge sort algorithm was invented by John von Neumann in 1945. It is an efficient sorting algorithm using a divide and conquer approach.

The Merge sort algorithm repeatedly divides the array into smaller chunks until we no longer divide the array into chunks.
Then it repeatedly merges the chunks of the array to get a sorted array.

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

First, we need to divide the array into smaller chunks until we no longer divide the array into chunks.

        left       right
       [3 , 4]     [2, 1]

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

We need to merge the smaller chunks to get the sorted array.

Compare 3 and 4 they are already sorted so that we moved 2 and 1 where 2 > 1 so put 1 first and second 2.

            left         right
           [3 , 4]     [ 2, 1 ]

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

           [3, 4]       [1 ,2]

Now, compare the left part index of 0 and right part index of 0 which are 3 and 1.

Where 1 is smaller than 3 so that we removed 1 from the right part and push into the sorted list.

          left         right
         [3 , 4]      [1, 2]

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

         [3, 4]         [2]

        sorted array  [ 1 ]

Again we checked 3 and 2 and removed 2 from the right part and push into the sorted list

          left          right
        [ 3 , 4 ]      [ 1, 2 ]

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

        [3, 4]            [ ]

        sorted array  [1,2]

Now, we need to merge the left part and right part with the sorted list.

          left         right
        [3 , 4]       [1, 2]

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

        [3, 4]         [ ]

        sorted array  [ 1 ,2 ,3, 4]

Algorithm implementation

Let’s implement a Merge sort algorithm in JavaScript.

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

  if(array.length < 2){
    return array  // it means we no longer divide the array
                  // into smaller chunks
  }

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

  return merger( mergeSort( left ),mergeSort( array ) )
}

In the above code, we are using a splice method to remove the left part of the array. The remaining part of the array is the right part.

Next, we need to implement a merger function which helps us to combine the left and right part of the array and returns the sorted list.

function merger(left, right) {
    const arr = [  ];
    while (left.length && right.length) {
        if (left[ 0 ] < right[ 0 ]) {
            arr.push( left.shift( ) ) // remove from the left part and push into
                                              //the sorted array
        } else {
            arr.push( right.shift(  ) ) // remove from the right part and push into
                                               //the sorted array
        }
    }
    return [ ...arr, ...left, ...right ];
}

Full code

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

  if(array.length < 2){
    return array
  }

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

  return merger(mergeSort(left),mergeSort(array))
}

function merger(left,right){

  const arr = [];

  while(left.length && right.length){
    if(left[0] < right [0]){
      arr.push(left.shift())
    }else{
      arr.push(right.shift())
    }
  }

  return [...arr,...left,...right];
}

console.log(mergeSort([10,5,3,8,2,6,4,7,9,1]));

//Output -> [1,2,3,4,5,6,7,8,9,10]