머지소트 병합정렬

function merge(left, right) {
  const sortedArr = [];
  while (left.length && right.length) {
    if (left[0] <= right[0]) { //계속 shift해주니까 0을 비교하는거임
      sortedArr.push(left.shift()); //왼쪽꺼가 더 작으면 왼쪽꺼 넣고
    } else {
      sortedArr.push(right.shift()); //오른쪽꺼가 더 작으면 오른쪽거 넣고
    }
  }
  //left,right 둘 중 하나는 요소가 남아있기 때문에 sortedArr 뒤에 붙여서 출력
  //비어있으면 spread Syntax에도 아무것도 없기 때문에 그냥 다 붙여준다.
  return [...sortedArr, ...left, ...right];
}

function mergeSort(arr) {
  if (arr.length === 1) return arr;
  const mid = Math.ceil(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
    //요소가 1개 일 때까지 재귀를 실행해 요소가 1개일 때 두 left,right부터
  	//차근차근 merge(정렬해서 합치기)해주면 된다.
  return merge(mergeSort(left), mergeSort(right));
}