mergeSort.js

/*-----------------------------------------------------------------------------
split, split til the end we merge them

the reference is from UdemyCourse: LearningAlgorithmsInJavascriptFromScratch
-----------------------------------------------------------------------------*/

/*＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

在cs50 2016 week3時學到的pseudocode
on input of a elements
  if n < 2 
    return
  else
    sort left half of elements
    sort right half of elements
    merge sorted halves
    
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊*/

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



function merge(arr1, arr2) {
  
  var result= [];
  
  while(arr1.length && arr2.length){
    var minElement;
    
    if(arr1[0] <arr2[0]) minElement = arr1.shift();
    else minElement = arr2.shift();
    
    result.push(minElement);
  }
  
  if(arr1.length) result = result.concat(arr1);
  else result = result.concat(arr2);
  
  return result;
  
}

mergeSort([8,4,2,3,1,7,5,6]);


/*-----------------------------------------------------------------------------
                    mergeSort
                        '
                      merge
               -------- ' --------
                   '          '
               mergeSort   mergeSort
                   '          '
                 merge      merge
     -------- ' --------   -------- ' --------
    mergeSort   mergeSort  mergeSort  mergeSort 

-----------------------------------------------------------------------------*/