Inserting and Sorting stuff(Merge Sort)

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s