[2022-12-29 ✍🏼 TIL ]

오늘은 합병 정렬(mergeSort)에 대한 강의를 들었습니다.

function merge(arr1, arr2) {
  let i = 0;
  let j = 0;
  let result = [];
  while (i < arr1.length && j < arr2.length) {
    if(arr1[i] < arr2[j]){
      //비교해서 
      //arr1[i]의 값이 작으면 배열에 넣고 
      //i 증가하기 j는 그대로
      result.push(arr1[i]);
      i++;
    }else if(arr2[j] <= arr1[i]){
      result.push(arr2[j]);
      //arr2[j]의 값이 작으면 배열에 넣고 
      //j 증가하기 j는 그대로
      j++;
    }
  }
  if(i < arr1.length) {
    result = result.concat(arr1.slice(i));
  }else if (j < arr2.length){
    result = result.concat(arr2.slice(j))
  }
  return result;
}

function mergeSort(arr) {
  if(arr.length <= 1){
    return arr;
  }
  let len1 = Math.floor(arr.length / 2);
  
  let left = mergeSort(arr.slice(0, len1))
  let right = mergeSort(arr.slice(len1))

  return merge(left, right)
    
}

console.log(mergeSort([1,2,5,22,9,32,110]))

이전에 재귀를 배웠던 것을 활용하여 구현해 보는 시간이였습니다.
재귀를 배우긴 했지만 알고리즘을 생각해내기 어려웠습니다.

그래도 이 알고리즘이 구현이 이해가 되기 때문에 다행히이라고 생각이 듭니다.
휴..😌