Hello Guys today i am going to show you how to apply merge sort algorithm in javascript

Lets get started...

Merge sort is a sorting algorithm that uses the “divide and conquer” concept.

Given an array, we first divide it in the middle and we get 2 arrays.

We recursively perform this operation, until we get to arrays of 1 element.

Then we start building up the sorted array from scratch, by ordering the individual items we got.

Suppose our array is this:

[4, 3, 1, 2]

We first divide the array into 2 arrays:

[4, 3]
[1, 2]

then we recursively divide those arrays:

[4]
[3]

and

[1]
[2]

Then it’s time to construct the result, by ordering those pairs of elements first:

[3, 4]
[1, 2]

Then we merge those 2 arrays:

[1, 2, 3, 4]

Example Code -

const merge = (leftarr,rightarr) =>{
  if (!Array.isArray(leftarr) || !Array.isArray(rightarr)) throw `mergeArrays error. Both parameters must be Arrays, found ${typeof leftarr} and ${typeof rightarr}`
  const output = [];
  let leftindex = 0;
  let rightindex = 0;

  while(leftindex < leftarr.length && rightindex < rightarr.length){
    const leftel = leftarr[leftindex];
    const rightel = rightarr[rightindex];

    if(leftel < rightel){
      output.push(leftel);
      leftindex++;
    }
    else{
      output.push(rightel);
      rightindex++;
    }
  }

  return [...output,...leftarr.slice(leftindex),...rightarr.slice(rightindex)];
}


function MergeSort(Arr){
  if (!Array.isArray(Arr)) throw `mergeSort error. Parameter must be an Array, found ${typeof Arr}`;
  if(Arr.length <=1){
    return Arr;
  }
   try {

  const middle = Math.floor(Arr.length / 2);
  const leftarr = Arr.slice(0,middle);
  const rightarr = Arr.slice(middle);
  return merge(
    MergeSort(leftarr),MergeSort(rightarr)
    );
   }
   catch(error){
     console.error(`mergeSort error. ${error.message} in ${error.stack}`);
   }

}

const items = [110,91,144,125,90,81,44,156,101,169,25,49,36];

console.log(MergeSort(items));

Output -

[
   25,  36,  44,  49,  81,
   90,  91, 101, 110, 125,
  144, 156, 169
]

Explaination -

Firstly we have created an arrow function with two parameters namely "leftarr" and "rightarr" which indicates the left array which have elements from 0 index to the element before the middle index and second is right array which have elements from the index just after the middle index to the last index.We also checked that the passed parameters are arrow or not, if not then throw an error
Then inside the arrow function we have a created an empty array with name output and two variables namely leftindex and rightindex and initialised them with 0(these vairables are used in while loop to iterate over the array).
Then we have created a while loop with condition that the leftindex variable value should be less than the value of leftarray length and rightindex value should be less than right array length value.
Then we have created two variables for left and right element and it will check every element from both left and right array.
Then in if statement we will check each element from left and right array that whether the value of element in the left array is less than the value of element in the right array or not.If the element in left array is smaller than element in right array then we will push the left element in the "output" array and if the element in the left array is greater than the element in the right array then we will push the right element in the "output" array.In the end we will return all the elements sorted using spread operator.
Then we have created a function named MergeSort with one parameter namely "Arr", Inside this function firstly we will check that the array length is greater than 1 or not, if the length is 1 , then we will return the same array.We also checked that the passed parameters are arrow or not, if not then throw an error
Then we have created 3 variables -
The first variable is middle which have the value of middle index , we get the middle index using floor function and inside it we have divided the array length by 2.
Then the second and third variable is leftarr and rightarr, which have the elements for left and right array and we will pass these arrays as parameters in our "merge" arrow function using recursion.

THANK YOU FOR READING THIS POST , AS I AM NEW TO DATA STRUCTURE AND ALGORITHM SO, IF YOU FIND ANY MISTAKE OR WANTS TO GIVE SUGGESTION PLEASE MENTION IT IN THE COMMENT SECTION

Merge Sort Algorithm in Javascript