Updated April 15, 2023
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 in 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, then 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 lists.
Now, we will see and apply the E technique to 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 points at the first position of List 1, and a Second pointer points at the first position of List 2.
4. Then, we will compare the value of both pointers. The pointer with a lesser value copies that element into List 3 and moves the pointer to the right of the list with a 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.
Pseudo code:
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.
Pseudo code:
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 the top-down Merge Sort implementation. It starts at the top and proceeds downwards, with each recursive turn asking the same question, “What is required to be done to sort the list?” and 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:
Code:
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 at 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 the 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
The properties of merge sort are as follows:
- 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 is not to be used in complex problems where space is a premium.
- The overall time complexity of the Merge sort is O(nLogn). It is more efficient than 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 understand different sorting algorithms thoroughly.
Recommended Articles
This has been a guide to Merge Sort in JavaScript. Here we discuss a basic concept and implementation along with properties, respectively. You can also go through our other suggested articles to learn more –
