Merge Sort

Merge Sort

its a divide and conquer type algorithm.

just break down your array into small and small pieces and until you have one items in each pieces. then merge together by comparing them. If you still have hard time to figure out what i am talking about, look at merge sort gif taken from wikipedia

Code Merge Sort: Merge sort has two parts. Main part does divide or breaks down and second part is merging/combining parts. At the time of combining, parts are combined together.

Divide: the first function named as mergeSort is actually a divide function. where an array is divided into two.

merge: this is just merging two sorted array. Just be careful this two array could be in different size

	function mergeSort(arr){
	   var len = arr.length;
	   if(len < 2){
		      return arr;
		 }
	   var mid = Math.floor(len/2);
	   var left = arr.slice(0,mid);
	   var right =arr.slice(mid);
	   return merge(mergeSort(left),mergeSort(right));
	}
	        

	function merge(left, right){
	  var result = [];
	  var lLen = left.length;
	      var rLen = right.length;
	      var l = 0;
	      var r = 0;
	  while(l < lLen && r < rLen){
	     if(left[l] < right[r]){
	       result.push(left[l++]);
	     }
	     else{
	       result.push(right[r++]);
	    }
	  }
	  return result.concat(left.slice(l)).concat(right.slice(r));
	}
		        

ref: merge sort