## Introduction to Merge Sort in JavaScript

Sorting algorithms are very important in Computer Science. The output of sorting is to arrange the elements of a list to a certain order (either ascending or descending). Merge Sort in JavaScript is one of the most efficient sorting algorithms available as it is based on the concept of divide and conquers. As the name suggests, first divide the bigger problem into small problems than solve the smaller problems in order to solve the bigger problem. Conceptually, Merge sort is a combination of two basic algorithms called MERGE and MERGE_SORT.

which works as follows:

- Divide the unsorted list into n number of single-item sub lists (n is the total number of elements in the unsorted list).
- Repeatedly merge sublists into sorted sublists until there is only one sorted list.

### Implementation of Merge Sort in JavaScript

The MERGE algorithm follows the procedure of combining two sorted lists into one sorted list.

**Example:** Suppose there are two lists i.e. List 1 {1,5,3} and List 2 {7,2,9}.

1. First sort both the lists.

Now, we will see and apply the E technique on it.

2. Then, we will create a new list of size x+y where x is the number of elements in List 1 and y is the number of elements in List 2.

In our case x=3 and y=3, so x+y= 6.

3. Now, we have two pointers.

A first pointer pointing at the first position of List 1 and Second pointer pointing at the first position of List 2.

4.5 (1,992 ratings)

View Course

4. Then we will compare the value of both pointers. The pointer with lesser value, copy that element into List 3 and move the pointer to the right of the list with smaller value and the resultant list (i.e. List 1 and List 3)

5. Similarly, perform step 4 again and again.

Further traversing…..

**Note**: If one of the lists (i.e. list 1 or list 2) gets fully traversed as in the case, then copy the entire content of another list from the pointer to the result list (i.e. list 3) as follows.

** **

**Pseudocode**

`Function merge (sublist1, sublist2) {`

Create var for result list

While sublist1 length > 0 and sublist2 length > 0

If sublist1[0] < sublist2[0]
Copy the sublist1 pointer value to result list and Shift pointer of sublist1 to right

else

Copy the sublist2 pointer value to result list and Shift pointer of sublist2 to right

Return concat sublist1 or sublist2 (depending if node1 is empty or not)

The MERGE_SORT algorithm divides the given unsorted list to minimum size and then calls the MERGE algorithm to combine the list into the new sorted list.

**Pseudocode**

`function mergeSort(list) {`

If list length < 2

Return list

Create var for middle index of list

Create var for left index of list

Create var for right index of list

Recursively call mergeSort function

}

**Example**

Here we are following top-down Merge Sort implementation. It starts at the top and proceeds towards downwards, with each recursive turn asking the same question “What is required to be done to sort the list?” and having the answer is “Split the list into two, make a recursive call and merge the results”.

**Code in Javascript**

`// Split the list into halves and merge them recursively`

function mergeSort (list) {

if (list.length < 2) {

return list;// return once we hit a list with a single element

}

var mid = Math.floor(list.length / 2);

var left = mergeSort(list.slice(0, mid));

var right = mergeSort(list.slice(mid));

return merge(left, right);

}

// compare the lists element by element and return the concatenated resultList

function merge (sublist1, sublist2) {

var resultList = [];

while (sublist1.length > 0 && sublist2.length > 0)

resultList.push(sublist1[0] < sublist2[0]? sublist1.shift() : sublist2.shift());

return resultList.concat(sublist1.length? sublist1 : sublist2);

}

const list = [6,5,3,1,8,7,2,4,2,5,1,2,3]
console.log(mergeSort(list)) //[ 1, 1, 2, 2, 2, 3, 3, 4, 5, 5, 6, 7, 8 ]

**
**The main function of the merge sort will divide the given list into smaller lists in every iteration of the recursive call. Don’t forget that recursion requires the base condition in order to avoid infinite recursion. In our case, we have:

`if (list.length < 2) {`

return list;// return once we hit a list with a single element

}

After we set up the base condition for recursion, then we will identify the middle index to split the given list into the left and right sub-list as you can see above in the example diagram. Then we need to merge the left sub-list and the right sub-list which we will look now, In the merge function above, we need to make sure that we are sorting all the elements in the left sub-list and right sub-list. The way we will do this is by using a while loop. Within the while loop, we will compare the element in the left sub-list and element in the right sub-list one by one. We can push the smaller of the two into the result list and move the cursor of the left sub-list and right sub-list accordingly. Finally, we need to concatenate the result list. This is very important! If we don’t do this last step here, we will have an incomplete list of elements at the end because the while loop condition will fail once any one of the two pointers reaches the end.

**Output:**

### Properties of Merge Sort

- Merge sort is stable as the same element in an array maintains their original positions with respect to each other.
- Merge sort is not ‘in place’ as during merging it creates a copy of the entire list is sorted. Due to this, the space complexity (O(n)) of this algorithm is actually greater than others, and not to be used in complex problems where space is premium.
- The overall time complexity of Merge sort is O(nLogn). It is more efficient as it is in the worst case also, the runtime is O(nlogn).

### Conclusion

Merge sort best, worst and average-case time complexities are the same which makes it a more efficient algorithm. It works faster than other sorting techniques. Merge sort can be applied to files of any size. It is highly parallelizable due to the use of the divide-and-conquer method. In order to develop strong basics in computer science, you are advised to thoroughly understand different sorting algorithms.

### Recommended Article

This has been a guide to Merge Sort in JavaScript. Here we discuss Introduction to Merge Sort in JavaScript and the Implementation along with Properties. You can also go through our other suggested articles to learn more –