• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

병합정렬 질문 있습니다

23.10.23 17:12 작성 조회수 130

2

강의 6:34까지 재귀함수로 배열의 반반을 원소 1개씩으로 분할하는 것 까지는 이해가 가는데, 왜 병합되어 정렬이 완료되는지는 이해가 안갑니다. ㅠㅠ

 

function MergeSort(arr, leftIndex, rightIndex){
if(leftIndex < rightIndex){
let midIndex = parseInt((leftIndex + rightIndex) / 2);
MergeSort(arr, leftIndex, midIndex);
MergeSort(arr, midIndex + 1, rightIndex);
}
}

까지는 분할만 이루어진 것 아닌가요?

아니면 분할+병합이 이루어져있다고 가정하는 건가요?

 

감사합니다.

답변 2

·

답변을 작성해보세요.

0

Chris Kim님의 프로필

Chris Kim

2024.02.12

이게 저도 이해가 안 갔었는데 MergeSort 재귀 호출한 부분에서 정렬이 된 것처럼 설명이 되어있어서 오해의 소지가 있을 거 같습니다. 재귀에 Merge 구현 전까지는 정렬이 안되어 있다고 봐야하지 않을까 싶습니다.

0

안녕하세요 김예서님.

Merge() 함수 호출 전에 호출한 두 개의 MergeSort()함수도 내부에선 Merge()를 실행하기 때문에 분할+병합이 모두 이루어졌다고 생각하셔야 합니다.

이것 때문에 재귀를 이해하는게 어렵지요 ㅎㅎ

궁금증이 해결되셨나요? 😊