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

Codepen demo

Tested using mocha and chai

How rotate an image continuously in CSS

In this demo, we are going to learn about how to rotate an image continuously using the css animations.

How to create a Instagram login Page

In this demo, i will show you how to create a instagram login page using html and css.

How to create a pulse animation in CSS

In this demo, i will show you how to create a pulse animation using css.

Creating a snowfall animation using css and JavaScript

In this demo, i will show you how to create a snow fall animation using css and JavaScript.

Top Udemy Courses

JavaScript - The Complete Guide 2023 (Beginner + Advanced)
116,648 students enrolled
52 hours of video content
\$14.99 FROM UDEMY
React - The Complete Guide (incl Hooks, React Router, Redux)
631,582 students enrolled
49 hours of video content
\$24.99 FROM UDEMY
Vue - The Complete Guide (w/ Router, Vuex, Composition API)
203,937 students enrolled
31.5 hours of video content
\$14.99 FROM UDEMY