mergeSort

Mergesort is an optimized sorting algorithm which is a common choice to implement `sort` methods in standard libraries as an alternative to quicksort or heapsort.

Mergesort uses a divide-and-conquer strategy. It begins by treating the input list of length N as a set of N “sublists” of length 1, which are considered to be sorted. Adjacent sublists are then “merged” into sorted sublists of length 2, which are merged into sorted sublists of length 4, and so on, until only a single sorted list remains. (Note, if N is odd, an extra sublist of length 1 will be left after the first merge, and so on.)

Time complexity: The entire input must be iterated through n, and you’re narrowing the workload by half every time you merge so n * logn = O(nlogn).

  1. Split array in halfScreen Shot 2018-01-09 at 9.10.16 AM
  2. Recursively sort each half
  3. Merge sorted arrays into larger sorted arrayScreen Shot 2018-01-09 at 9.11.20 AM.png

This can be implemented using either a recursive (“top-down”) or an iterative (“bottom-up”) approach.

Recursive Solution:

var mergeSort = function(array) {
  if (array.length < 2) {      
    return array;   
  }   

  var mid = Math.floor(array.length / 2);   
  var left = array.slice(0, mid);   
  var right = array.slice(mid);   
  return merge(mergeSort(left), mergeSort(right)); 
}; 

var merge = function (left, right) {   
  var output = [];   
  var i = 0;    
  var j = 0;   

while (left.length > i && right.length > j) {
    if (left[i] < right[j]) {
      output.push(left[i]);
      i++;
    } else{
      output.push(right[j]);
      j++;
    }
  }

  return output.concat(left.slice(i)).concat(right.slice(j));
}

 

Advertisements
mergeSort

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s