Merge Sort Algorithm in Javascript

#javascript #algorithms #programming #productivity

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

Top comments (3)

JoelBonetR 🥇 • Jul 18 '22 • Edited

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:

To TS or not to TS, that is NOT the question. Is it?

JoelBonetR ・ Apr 26 ・ 4 min read

#javascript #typescript #discuss #devjournal

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));

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 😊