Algorithm problem-20

1. 문제

• 주어진 배열을 병합정렬로 정렬하여 리턴하라

2. 시도

• arr를 최소 단위로 나누고, 전부 나눈 상태에서 순차적으로 재조립
• 재조립할 때에 정렬을 시켜서 조립하면 마지막에는 정렬된 배열이 나오겠지
• 중간점을 찾아서 나누고, 또 나누고, 또 나누고?
• 반복보다는 재귀가 이해는 쉬운 것 같다
• 베이스 케이스를 길이가 1이 될 때까지로 하고
• 중간점을 찾아, 기준으로 좌, 우로 나누고
• 좌, 우를 또 재귀로 나눠주면서 병합을 해줘야 하니까
• 정렬시키는 내부 함수를 만들어줘서 정렬함수에 나눈 애들을 재귀로 넣어서 리턴하면 되려나..

3. 수도코드

const mergeSort = function (arr) {
  // 나눈 애들을 정렬시키는 함수식, 처음에는 내부 함수로 구현하였음
  // 내부 함수로도 해보고, 위에도 구현해봤는데, 아래에 구현해야만 작동함, 왜일까?
  // 스코프나 데이터 흐름의 문제일 것으로 생각되는데
  const sorter = (left, right) => {
    let result = [];
    // 둘을 비교해서 작은 걸 결과에 담고, 둘 중 하나의 길이가 0이 되면 끝내고
    // 그 때의 3개 배열을 합쳐서 리턴하면 정렬 상태
    while (left.length > 0 && right.length > 0) {
      if (left[0] <= right[0]) {
        result.push(left.shift());
      } else {
        result.push(right.shift());
      }
    }
    return [...result, ...left, ...right]
  }
  // base case, 배열의 길이가 1 또는 0일 때, 홀수 배열을 나눌 때를 생각해야함
  if (arr.length <= 1) return arr;
  // mid, left, right
  let mid = Math.floor(arr.length / 2);
  let left = arr.slice(0, mid)
  let right = arr.slice(mid)
  // return을 재귀로 해야 함, 정렬식에 넣어서 arr를 합쳐서 리턴시키면 될 듯?
  return sorter(mergeSort(left), mergeSort(right));
};

4. 레퍼런스

const mergeSort = function (arr) {
  if (arr.length <= 1) return arr;
  let mid = Math.floor(arr.length / 2);
  let left = arr.slice(0, mid)
  let right = arr.slice(mid)
  return sorter(mergeSort(left), mergeSort(right));
};
const sorter = (left, right) => {
  let result = [];
  while (left.length > 0 && right.length > 0) {
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  return [...result, ...left, ...right]
}