Merge Sort Using Javascript

Simple example of merge sort

Merge sort is a sorting algorithm that works on a divide and conquer approach. This algorithms work with splitting the array equally to its last element and then merging the array in sorted format.

Let’s take an example for [-6, 20, 8, 4, -2]

Steps:

• Divide the array in two equal parts (we need to keep dividing until we reach the last element in the array)

[-6,20] [8,4,-2]

• Array has more than 1 element, divide again

[-6] [20] [8] [4,-2]
[-6] [20] [8] [4] [-2]

Now we have multiple array with one element, we need to work on merging the sub array to create a single array with sorted values.

For merging, we’ll take two array at a time, let’s suppose a leftArray and rightArray. We’ll initialise a tempArray to store sorted Values.

leftArray = [-6]
rightArray = [20]

We’ll create a while loop until we have an empty array.

let tempArray = []
while(leftArray.length && rightArray.length){
  if(leftArray[0] <= rightArray[0]){
   // if left array has lesser value
   tempArray.push(leftArray.shift()); // we are pushing the first    element from leftArray to temporary Array and removing that element from leftArray
   } else{
 // tempArray.push(rightArray.shift()); // we are pushing the first element from rightArray to temporary array and removing that element from rightArray
   }
}

Once we are done with the comparison, we need to return the updated array with left over element from either left or right array

return [...tempArray,...leftArray,...rightArray];

This will give us the result as [-6,20], which is a sorted array. we’ll use the same approach with other sub arrays as well.

Let’s jump into the code.

Below is the implementation of merge Sort. For the implementation, we’ll create two functions:

• One to Split the unsorted array into sub arrays.
• Other to merge the sub array to create a sorted array.

Creating a function to split the unsorted array in sub arrays:

/**
* This function will split the array to its sub arrays with only one  * element.
*/
const splitUnsortedArray = (unSortedArray) =>{
    // checking if array has only one element
    if(unSortedArray.length <2){ return unSortedArray};
    // Dividing the array in two parts
    const mid = Math.floor(unSortedArray.length/2);
    const leftArray = unSortedArray.slice(0,mid);
    const rightArray = unSortedArray.slice(mid);
    // calling the function recursively to get down to divide array to last element
return  merge(splitUnsortedArray(leftArray),splitUnsortedArray(rightArray));
}

Creating a function to merge the Split array

const merge = (leftArray, rightArray) =>{
let tempArray = [];
while(leftArray.length && rightArray.length){
  if(leftArray[0] <= rightArray[0]){
   // if left array has lesser value
   tempArray.push(leftArray.shift()); // we are pushing the first    element from leftArray to temporary Array and removing that element from leftArray
   } else{
 // tempArray.push(rightArray.shift()); // we are pushing the first element from rightArray to temporary array and removing that element from rightArray
   }
   
  return [...tempArray,...leftArray,...rightArray];
}

Merge sort has a time complexity of O(nlog(n)).

Stay tuned for more to come, If you are new here, do checkout our Algorithms using Javascript blog, we are covering few of the most commonly used algorithms using javascript.

In the next blog, we’ll go through Selection sort.