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]
 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]
Codepen demo
Tested using mocha and chai