Merge Sort in JavaScript

Merge Sort is executed in O (n log n) time. It’s very effective. Merge Sort is a recursive algorithm used for merge that relies on the Divide and Conquers technique. An array of elements is divided into two smaller sub-arrays. Once these two arrays are freed independently, they are able to produce the sorted array. The merge process can be performed recursively until there is only one element in the array.
 

Algorithm:

sort(arr[], g, d)
Si d > g
   1. Find the middle to divide the array into two halves m = (g + d) / 2.
   2. Call the sort method for the first half.
   3. Call the sort method for the second half.
   4. Merge the two halves sorted in steps 2 and 3.

 

Example :

 
 

Script to sort array elements using merge sort

function merge(left, right){
	
    var arr = [], l = 0, r = 0;

    while (l < left.length && r < right.length){
        if (left[l] < right[r]){
            arr.push(left[l++]);
        } else {
            arr.push(right[r++]);
        }
    }
    return arr.concat(left.slice(l)).concat(right.slice(r));
}

function sort(arr){

    if (arr.length < 2) {
        return arr;
    }

    var mid = Math.floor(arr.length / 2),
        right = arr.slice(mid),
        left = arr.slice(0, mid),
        p = merge(sort(left), sort(right));
    
    p.unshift(0, arr.length);
    arr.splice.apply(arr, p);
    return arr;
}

var arr = [5, 8, 11, 6, 1, 9, 3];
sort(arr);
console.log(arr);

Output:

[1, 3, 5, 6, 8, 9, 11]

 
The merge() function merges two arrays, “left” and “right”. The “l” variable keeps track of the index to compare for the “left” array while the “r” variable does the same for the “right” array. Each time a value is added to the array, its corresponding index variable is incremented. As soon as one of the arrays is exhausted, the remaining values ​​are appended to the end of the “arr” array using concat() in line 12.

The merge() function is quite simple, but you have to combine the two sorted arrays. As mentioned earlier, this is done by dividing the array into multiple arrays and then systematically combining them. This is easily done using a recursive algorithm as mentioned in the sort() function.

The sort() function stores the results of the sort in a variable called “p”. The best way to replace elements in an array is to use the splice() method, which accepts two or more arguments. The first argument is the index of the first value to replace and the second argument is the number of values ​​to replace. The next argument is the value to insert at this position. Since there is no way to pass an array of values ​​into splice(), you must use apply() and pass the first two arguments combined with the sorted array.
MCQPractice competitive and technical Multiple Choice Questions and Answers (MCQs) with simple and logical explanations to prepare for tests and interviews.Read More