DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

Cover image for Merge Sort Algorithm in Javascript
Mysterio
Mysterio

Posted on • Updated on

Merge Sort Algorithm in Javascript

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]
Enter fullscreen mode Exit fullscreen mode

We first divide the array into 2 arrays:

[4, 3]
[1, 2]
Enter fullscreen mode Exit fullscreen mode

then we recursively divide those arrays:

[4]
[3]
Enter fullscreen mode Exit fullscreen mode

and

[1]
[2]
Enter fullscreen mode Exit fullscreen mode

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

[3, 4]
[1, 2]
Enter fullscreen mode Exit fullscreen mode

Then we merge those 2 arrays:

[1, 2, 3, 4]
Enter fullscreen mode Exit fullscreen mode

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));
Enter fullscreen mode Exit fullscreen mode

Output -

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

Explaination -

  1. 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

  2. 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).

  3. 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.

  4. Then we have created two variables for left and right element and it will check every element from both left and right array.

  5. 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.

  6. 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

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

Top comments (3)

Collapse
 
joelbonetr profile image
JoelBonetR • Edited on

As you are learning JavaScript I recommend you to add a bit of robustness to your code by ensuring that what you receive on a given function is effectively what you expect it to receive and that it returns what you expect it to return. Otherwise it can become a mess while you code bigger projects.

Take a look at:

Here's your code after a refactor:

// @ts-check

/**
 * Merges two arrays
 * @param {Array<number|string>} l
 * @param {Array<number|string>} r
 * @returns
 */
const mergeArrays = (l, r) => {
  if (!Array.isArray(l) || !Array.isArray(r)) throw `mergeArrays error. Both parameters must be Arrays, found ${typeof l} and ${typeof r}`;
  let out = [],
    li = 0,
    ri = 0;

  try {
    while (li < l.length && ri < r.length) {
      const le = l[li],
        re = r[ri];

      if (le < re) {
        out.push(le);
        li++;
      } else {
        out.push(re);
        ri++;
      }
    }

    return [...out, ...l.slice(li), ...r.slice(ri)];
  } catch (error) {
    console.error(`mergeArrays error. ${error.message} in ${error.stack}`);
    return [];
  }
};

/**
 * Implements the merge sort algorithm
 * @param {Array<number|string>} arr
 * @returns {Array<number|string>}
 */
const 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 m = Math.floor(arr.length / 2),
      l = arr.slice(0, m),
      r = arr.slice(m);

    return mergeArrays(mergeSort(l), mergeSort(r));
  } catch (error) {
    console.error(`mergeSort error. ${error.message} in ${error.stack}`);
    return [];
  }
};

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

console.log(mergeSort(items));
Enter fullscreen mode Exit fullscreen mode

Forget the variable name changes, i wrote it by hand instead copy-pasting, the original ones are more understandable and OK.

This way we avoid passing non-array values into functions that are dependant on arrays, if it happens we can then know super fast where the issue happened plus, it won't break in more errors into caller functions as it always returns an Array.

Moreover, as setting the TS pragma at the top of the file, VSCode will handle it out of the box and bother you if you try to pass something wrong to the functions like an array that's not numbers or strings (I mean, IRL you can sort booleans with this but what's the point? πŸ˜‚).

As bonus I'm not aware if you know about the pre-increment. It does not matter in this use-case, but on a future algorithm it may come in handy 😊

Collapse
 
shubhamtiwari909 profile image
Mysterio

Sure I will check this and thank you for giving an improved version of my code
I really appreciate it

πŸ‘‹ Hey, my name is Noah and I’m the one who set up this ad. My job is to get you to join DEV, so if you fancy doing me a favor, I’d love for you to create an account.

If you found DEV from searching around, here are a couple of our most popular articles on DEV: