Merge Sort

complexity : nlogn

by bhupendra negi

JavaScript

//TASK: implement mergesort!
// protip: Split the array into halves and merge them recursively 
// protip: return once we hit an array with a single item. That is a sorted array of size 1!
// protip: compare the arrays item by item and return the concatenated result



const mergesort = (arr) => {
  let n = arr.length;
  // base case : if no of elemnts in array is 1 then return
  if (n<2) return arr;
  let mid = Math.floor(n/2);

  let left = arr.slice(0,mid);
    //console.log(left);
  let right = arr.slice(mid,n);
 // console.log(right);
  let leftMergeSort = mergesort(left);
   console.log(leftMergeSort);
  let rightMergeSort = mergesort(right);
  return merge(leftMergeSort,rightMergeSort);

}

const merge = (arr1,arr2) => {
  let merged = [];
  console.log('arr1 :');
  console.log(arr1);
  console.log('arr2 :');
  console.log(arr2);
  while (arr2.length || arr1.length ) {
    let a1 = arr1[0] ;
    let a2 = arr2[0] ;
    let insert;
    let eq = 0;
    if (a1 > a2) {
      // take from a2; remove first elment from a2    
      console.log('a2 pop')       
      insert = arr2.shift(); 
      //console.log(insert)  ;      
    }
    else if (a2>a1) { 
      console.log('a1 pop')     
       insert = arr1.shift();   
    }
    else if (a1 == a2) {
      // remove elemnts from both
      console.log('equal');   
      insert = arr1.shift();           
      arr2.shift();   
      merged.push(insert);
    }
    else {
      insert =  arr1.shift();
      if (!insert) insert =  arr2.shift();      
      }
    console.log("insert :" + insert);
    merged.push(insert);     
  }
  return merged;
}

/*const result = merge([1,2,2,3],[5])
console.log('result')
console.log(result); */
const result = mergesort([-9,2,-5,6,-8,1,2,-1])
console.log(result);