### Merge sort is a highly intuitive and easy to learn algorithm.

Basic principle here is divide and conquer , what we want to do is divide the array unitl only one element remains then compare it to the next element merge the compared array in right order then move onto the next pair of array.

Algo:Step 1 :If length of array is less than 2 return the array. STEP 2 :divide the array in half by recursively acalling the same mergeS function on both half. STEP 3 :return the merged array.

function mergeS(arr) { if (arr.length < 2) return arr; var middle = parseInt(arr.length / 2); var left = arr.slice(0, middle); var right = arr.slice(middle, arr.length); return mergeArrays(mergeS(left), mergeS(right)); } function mergeArrays(left, right) { var result = []; while (left.length && right.length) { if (left[0] <= right[0]) { result.push(left.shift()); } else { result.push(right.shift()); } } while (left.length) result.push(left.shift()); while (right.length) result.push(right.shift()); return result; } console.log(mergeS([3435, 6, 43, 95, 30, 940, 421, 56, 6]));

You can paste the same code in your browser’s console and run it directly.

The time complexity of this algo is O(nlogn).

Enjoy!

Advertisements