by Sai gowtham

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.

  • 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]

  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]
  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]

JavaScript merge sort example

Codepen demo

Tested using mocha and chai

Top Udemy Courses

JavaScript - The Complete Guide 2020 (Beginner + Advanced)
JavaScript - The Complete Guide 2020 (Beginner + Advanced)
45,614 students enrolled
52 hours of video content
View Course
React - The Complete Guide (incl Hooks, React Router, Redux)
React - The Complete Guide (incl Hooks, React Router, Redux)
284,472 students enrolled
40 hours of video content
View Course
Vue JS 2 - The Complete Guide (incl. Vue Router & Vuex)
Vue JS 2 - The Complete Guide (incl. Vue Router & Vuex)
130,921 students enrolled
21 hours of video content
View Course