## DEV Community is a community of 870,143 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Dumb Down Demistifying Dev

Posted on • Updated on

# Merge Sort

What do we understand about Merge Sort?

• This is a Divide & Conquer algorithm
• It usually comprises of 2 functions
• main function recursively splits the Array into 2 halfs before merger
• 2nd function is the actual merge function where it compares the left Array values with the right Array values
• there should be a counter that acts as the pointer for the 2 half Arrays
• returns a new Array instead of mutating the original Array
• Good resource to continue reading up on:

• Time Complexity:

• Height of the tree refers to the recursion part of the function - O(logn)
• Merge helper function - O(n)
• MergeSort worst - O(nlogn)
• Space Complexity:

• O(n)
``````    function merge (left, right) {
let x = 0;
let y = 0;
let output = [];

//! we check both the left and right pointers
//! if they have reached the end of their respective Arrays
while (x < left.length && y < right.length) {
//! COMPARE
if (left[x] < right[y]) {
output.push(left[x]);
x++;        // next value to check if it is also smaller
} else {
output.push(right[y]);
y++;        // bigger values comes in here
}
}

// left side leftovers from first loop
while (x < left.length) {
output.push(left[x]);
x++;
}

// right side leftovers from first loop
while (y < right.length) {
output.push(right[y]);
y++;
}

return output;
}

function MergeSort(arr, start = 0, end = arr.length) {
const arrayLength = arr.length;
if (arrayLength < 2) return arr;

const midindex = Math.floor(arrayLength / 2);
const left = MergeSort(arr.slice(start, mid));
const right = MergeSort(arr.slice(mid + 1, end));

return merge(left, right);
}
``````