Merge Sort is one of many sorting techniques. It's said to be one of the fastest sorting techniques. In this article, we'll learn about Merge Sort- its algorithm and how it works with an example.
What is sorting?
Sorting means placing elements of a list in a specific or particular order. The order can be numerical, alphabetic, or alphanumeric. Like other programming language, using JavaScript also we can perform sorting operation. Among all these, the merge sort is one of the robust way o sorting large data structure elements.
What is Merge sort?
Merge Sort is a sorting technique that uses a divide-and-conquer approach to sort the provided list of elements. The algorithm splits the array into subarrays to sort the items.
- Its best-case complexity is O(n*logn) which occurs when the array is sorted already.
- Its average-case complexity is O(n*logn) which happens when the array elements are jumbled.
- Its worst-case complexity is O(n*logn) which happens when the array elements must get sorted in reverse order.
It has a space complexity of O(n).
Algorithm of Merge Sort
Here is an algorithm for Merge Sort:
Algorithm:
Msort(array, left, right)
if left< right
set mid = (left+ right)/2
Msort(array, left, mid)
Msort(array, mid + 1, right)
Msort(array, left, mid, right)
END
Working of Merge Sort
We already read above that Merge Sort uses the divide and conquer technique to sort the elements. Here are the steps that Merge Sort takes to sort an array:
- Merge Sort splits the list into two halves.
- Division of the subarray continues until there are only single elements left.
- Beginning with the single element arrays, merge the subarrays in sorted order.
- Step 3 gets repeated until the array gets sorted.
Let's take the array below as an example:
12, 31, 25, 8, 32, 17, 40, 42
we'll divide the above array into two parts and keep dividing the list into equal parts until it remains with single elements.
As the number of elements is 8, so they will get divided into two parts of size 4
12, 31, 25, 8 32, 17, 40, 42
Now the array will get divided into four parts of size 2
12, 31 25, 8 32, 17 40, 42
We'll keep dividing the array until we get the single values.
12 31 25 8 32 17 40 42
Now we'll similarly combine them by comparing them with one another and putting them in sorted order.
In the first iteration, we'll compare 12 with 31, and there will be no change since 12 is smaller than 31.
Next, comparing 25 with 8, since the number 8 is smaller than 25, we'll put 8 followed by 25.
Similarly, we'll put 17 first followed by 32, and keep 40 and 42 in the same order.
12, 31 8, 25 17, 32 40, 42
In the same manner, we'll compare the array with 2 data values and put them in the sorted order as shown below:
8, 12, 25, 31 17, 32, 40, 42
In the final merging of arrays, after sorting the entire array. The array will look like this:
8 12 17 25 31 32 40 42
Merge sort implementation in JavaScript
Here is the code for implementing Merge Sort in JavaScript.
Code:
<html>
<body>
<script>
// arr[l..m] for first sub array, arr[m+1..r] for second...
function merge(arr, l, m, r)
{
var n1 = m - l + 1;
var n2 = r - m;
var L = new Array(n1);
var R = new Array(n2);
for (var i = 0; i < n1; i++)
L[i] = arr[l + i];
for (var j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
// Merging the arrays back into arr[l..r]
var i = 0;
var j = 0;
// Initial index of merged subarray
var k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy the remaining elements of L[]
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy the remaining elements of R[]
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}}
function mergeSort(arr,l, r){
if(l>=r){
return;//returns recursively
}
var m =l+ parseInt((r-l)/2);
mergeSort(arr,l,m);
mergeSort(arr,m+1,r);
merge(arr,l,m,r);
}
// Function to print an array
function printArray( A, size)
{
for (var i = 0; i < size; i++)
document.write( A[i] + " ");
}
var arr = [12, 31, 25, 8, 32, 17, 40, 42];
var arr_size = arr.length;
document.write( "The array before sorting <br>");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
document.write( "<br>The array after sorting <br>");
printArray(arr, arr_size);
</script>
</body>
</html>
Output:
To sum up:
So here we are at the end of the article. We learned what merge Sort is and its algorithm, its time complexities, how it works, and a detailed explanation with an example. It is not the most efficient way of sorting but is surely one of the most widely used one.