Merge sort in Javascript

Hello folks! 👋, we all often run into the situation where we need an efficient algorithm for sorting. And today I'm implementing the Merge sort algorithm in JavaScript. With this, we can move from the O(n^2) algorithms to a much more scalable O(nlogn) solution.

Similar to binary search, merge sort is a divide and conquers algorithm. The goal is to break down our problems into sub-problems and recursively continue to break those down until we have a lot of simple problems that we can easily put back together.

Steps for Merge Sort

Merge sort divides the array into two sub-arrays and later divides each array into another two arrays and so on until a single element of array is left. For example the array [2, 5, 7, 3, 1, 9] divides into single array elements such as [2], [5], [7], [3], [1], [9].
It starts comparing array in such a manner that two arrays are compared and concatenated. In this example, it compares two arrays at a time that is [2], [5] are compared & concatenated then [7], [3] and so on such that the arrays [2,5], [3,7], [1,9] are formed.
It follows the same way that two arrays are compared and concatenated. So [2,5] & [3,7] are compared and merged to get an array as [2,3,5,7] and the same case with the last remaining array [1,9].
The same pattern is applicable here that is the remaining two arrays are compared and merged into the final single array as [1, 2, 3, 5, 7, 9].

function mergeSort(arr) {
    if(arr.length === 0 || arr.length === 1) return arr;

    const mid = Math.floor(arr.length/2); // get middle item of the arr & round it
    const left = mergeSort(arr.slice(0, mid)); // item on the left side
    const right = mergeSort(arr.slice(mid)); // item on the right side

    let result = [];
    let l = 0; // left index
    let r = 0; // right index

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

    result = result.concat(left.slice(l));
    result = result.concat(right.slice(r));
    return result;
}
console.log(mergeSort([2, 5, 7, 3, 1, 9])) 
// [ 1, 2, 3, 5, 7, 9 ]

Conclusion

While merge sort is the best algorithm we've covered so far since it's O(nlogn). it's good to keep in mind that it works better with larger amount data sets. If you don’t know how much data you’ll need to be sorted consider using another algorithm, like insertion sort.

If you like this article let me know in the comment section below or follow me on Twitter & Instagram.

How to implement Merge Sort in JavaScript?

Steps for Merge Sort

Conclusion