[알고리즘] 병합정렬 (Merge Sort)

병합정렬

분할 정복의 효과를 가장 잘 보여주는 대표적인 정렬 알고리즘

 

1.분할(Divide) : 

입력 리스트를 같은 크기의 2개의 부분 리스트로 분할한다.

 

2.정복(Conquer) : 

부분 리스트를 정렬한다

부분 리스트의 크기가 충분히 작지 않으면

순환 호출을 이용하여 다시 분할 정복 기법 적용

리스트의 크기가 1이면 이미 정렬 된 것!

 

3.병합(Combine, merge) : 

정렬된 부분 리스트들을 하나의 배열에 통합

 

알고리즘에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 병합하는 단계인 merge()이다

효율적인 병합을 위해서는 반드시 임시 리스트가 필요하다

병합은 각 부분 리스트의 첫 번째 항목부터 오른쪽으로 시작

두 부분 리스트의 항목 A[i] 와 A[j]를 비교하여 더 작은 요소를 먼저 새로운 리스트 sorted 에 복사