How implement merge sort algorithm in JavaScript

by Sai gowtham2min read
How implement merge sort algorithm in JavaScript

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

  1. Merge sort repeatedly divides the array into smaller chunks until we no longer divide the array into chunks.

  2. It repeatedly merges the chunks of the array to get the sorted array.


Example : [3,4,2,1]

1). First, we need to divide the array into smaller chunks.

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

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

2). we need to merge the smaller chunks to get the sorted array.

compare 3 and 4 they are already sorted next 2 and 1 put 1 first and second 2.

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

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

               [3, 4 ]          [1 ,2 ]

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

where 1 is smaller than 3 so we remove 1 from the right part and push into the sorted list.

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

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

              [3, 4 ]          [ 2 ]


        sorted array  [ 1 ]

again we check 3 and 2 and remove 2 from the right part and push into the sorted list

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

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

              [3, 4 ]           [  ]


        sorted array  [ 1 ,2 ]

Now add the left part and right part with the sorted list.

       left  [ 3 , 4 ]     right [ 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 it removes the left part of the array.so that 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.

JavaScript merge sort example

Code pen demo

Tested using mocha and chai