Algorithm 27 : mergeSort

🔒 설명

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

🔒 예시

let output = mergeSort([3, 1, 21]);
console.log(output); // --> [1, 3, 21]

🔒 생각

병합정렬은 배열을 왼쪽,오른쪽으로 재귀적으로 나눠 하나의 요소만 남을 때까지 반복하고, 이를 다시 정렬하면서 합치는 정렬 방법이다.

Javascript는 싱글스레드이기 때문에 기본적으로 한개의 작업만 반복한다. 그래서 재귀적으로 나눠질 때 정렬작업이 stack에 쌓이게 되고 최종적으로 재귀가 끝났을 때 stack이 순차적으로 실행됨을 생각하고 코드를 작성해야 한다. (나는 작성하지 못하고 페어분의 설명을 듣고 이해했다.)

🔑 풀이

const mergeSort = function (arr) {
  // TODO: 여기에 코드를 작성합니다.
  if (arr.length < 2) {
    return arr
  }
  let middle = parseInt(arr.length / 2)
  let left = arr.slice(0, middle)
  let right = arr.slice(middle)

  const merge = (left, right) => {
    let resultArr = [];
    let leftIndex = 0;
    let rightIndex = 0;
    while (leftIndex < left.length && rightIndex < right.length) {
      if (left[leftIndex] < right[rightIndex]) {
        resultArr.push(left[leftIndex])
        leftIndex++
      } else {
        resultArr.push(right[rightIndex])
        rightIndex++
      }
    }
  return resultArr.concat(left.slice(leftIndex),right.slice(rightIndex))
  }
  return merge(mergeSort(left),mergeSort(right))
};

💡 깨달은 점

배열을 쪼개고 그 안에서 인덱스를 정리하는 함수를 추가해야했다.
그리고 배열이 나눠지면서 merge 함수의 변수로 들어가는데,
여기서 제일 중요한 것이 merge함수가 실행되는 게 아니라 mergeSort(left),mergeSort(right) 변수가 재귀적으로 실행되기 때문에 merge함수를 실행하려는 코드는 stack에 계속 쌓이게 된다.
이게 나중에 arr.length < 2 조건이 맞을 때 재귀가 끝나게 되고,
이 때부터 가장 위에 쌓여있던 stack부터 실행, 즉 merge함수가 실행돼 부분정렬을 시작한다!!