토이 20번

문제

정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다.

주의사항

병합 정렬을 구현해야 합니다.
arr.sort 사용은 금지됩니다.
입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다.

풀이과정

잠깐 팁
정렬의 알고리즘과 시간복잡도

정답코드

const merge = function(left, rigth){
// 정렬이 되지 않은 두 배열을 파라미터로 넣어준다. 
// 두배열 첫번째 값을 비교해서 작은값을 배열에 넣어준다. 이걸 반복시킨다.
let merged = [];
let leftIdx = 0; 
let rigthIdx = 0;

// 반복시킬 크기를 만든다. 
const size = left.length + rigth.length 

for(let i = 0; i < size; i++){
  //조건은 왼쪽배열에 인덱스와 오른쪽 배열과 비교한다.
  if(leftIdx >= left.length){
    merged.push(rigth[rigthIdx]);
    rigthIdx++
  } else if(rigthIdx >= rigth.length || left[leftIdx] <= rigth[rigthIdx]){
    merged.push(left[leftIdx]);
    leftIdx++
  } else {
    merged.push(rigth[rigthIdx]);
    rigthIdx++
  }
}
return merged;

}


const mergeSort = function (arr) {
  // TODO: 여기에 코드를 작성합니다.
  // 입력된 배열을 반으로 나눈다.
  // 그리고 나눈 두배열을 비교해서 작은것을 결과를 보여줄 배열에 넣는다. 
  // 가장 기본 조건은 배열의 길이가 2보다 작으면 그대로 배열을 리턴한다. 
  // merge 함수를 만들어서 두 배열을 비교해서 병합하는 함수를 만든다. 
  if(arr.length < 2) return arr;
  
  //배열을 나눌때 소수점은 지우기 위해 파스인트를 사용한다.
  // 왼쪽 오른쪽을 재귀함수를 사용한다.
  const mid = parseInt(arr.length / 2)
  const left = mergeSort(arr.slice(0,mid));
  const rigth = mergeSort(arr.slice(mid));
  const merged = merge(left , rigth);
  return merged;
};