병합 정렬(merge sort)

•정의

가장 먼저 실전에 응용된 정렬 알고리즘.
분할과 정복이 핵심.

•코드

const mergeSort = () => {
  array = mergeSortRec(array);
}
let mergeSortRec = (array) => {
  let length = array.length;
  if(length === 1){
    return array;
  }
  let mid = Math.floor(length/2),
      left = array.slice(0, mid),
      right = array.slice(mid, length);
  return merge(lergeSortRec(left),mergeSortRec(right));
}
let merge = (left,right) => {
  let result = [],
      il =0,
      ir =0;
  while(il < left.length && ir < right.length){
    if(left[il] < right[ir]){
      result.push(left[il++]);
    }else{
      result.push(right[ir++]);
    }
  }
  while(il < left.length){
    result.push(left[il]);
  }
  while(ir < right.length){
    result.push(right[ir])
  }
  return result;
}