JS 노트 병합정렬

병합정렬
.
시간복잡도 O(n log n)
입력값을 2로 나누어 분할 -> 정복 하는 방식

let 입력값 = [12, 4, 3, 4, 6, 99, 123, 33, 42]

function 병합정렬(입력배열){
  let 입력배열의길이 = 입력배열.length;
  let 결과값 = [];
  
  if(입력배열의길이 <= 1){
    return 입력배열
  }
  
  let mid = parseInt(입력배열의길이/2);
  let left = 병합정렬(입력배열.slice(0, mid))
  let right = 병합정렬(입력배열.slice(mid))

  while(left.length !=0 && right.length !=0){
    if(left[0]<right[0]){
      결과값.push(left.shift())
    }else{
      결과값.push(right.shift())
    }
  }
  while(left.length!=0){
    결과값.push(left.shift())
  }
  while(right.length!=0){
    결과값.push(right.shift())
  }
  
  return 결과값
  
}

console.log(병합정렬(입력값))