Merge Sort is a Divide and Conquer algorithm. It splits the input array into 2 and calls itself recursively, then merges the 2 sorted halves. The Recursive calls and merging of sorted arrays are made in the merge function, sorting of arrays is done by the function mergeSort.
function mergesort(arr,start,mid,end) {
let n1 = mid - start + 1;
let n2 = end - mid;
let l = [];
let r = [];
for(let i = 0; i < n1; i++)
l[i] = arr[start+i];
for(let i = 0; i < n2; i++)
r[i] = arr[mid + 1 + i];
let i = 0,j = 0,k = start;
while(i < n1 && j < n2) {
if(l[i] > r[j]) {
arr[k++] = r[j++];
}
else (l[i] <= r[j]){
arr[k++] = l[i++];
}
}
while(i < n1){
arr[k++] = l[i++];
}
while(j < n2){
arr[k++] = r[j++];
}
return;
}
function merge(arr,start,end) {
if(start < end) {
let mid = Math.floor((start+end)/2);
merge(arr,start,mid);
merge(arr,mid+1,end);
mergesort(arr,start,mid,end);
return;
}
else
return;
}
function mergeMain(arr){
var start = 0;
var end = arr.length -1;
merge(arr, start, end);
return arr;
}
Best Case : Ω (n log(n))
Average Case : θ (n log(n))
Worst Case: O (n log(n))
O(n)
** where n is the length of the array