[알고리즘] 병합 정렬 - 분할해서, 정렬하며 합치다

병합정렬

여러개의 정렬된 자료를 병합해서 하나로 만든다

부분집합으로 분할하고, 각 부분집합에서 정렬을 완료하고 정렬된 부분집합을 결합

 

• 2-way 병합: 2개의 정렬된 자료를 1개로 병합
• n-way 병합: n개의 정렬된 자료를 1개로 병합

 

2-way만 한번 알아보자

 

1. 같은 크기의 부분집합 2개로 분할
2. 부분집한 원소들 정렬
3. 1개로 병합

예시

분할 단계

44, 88, 62, 38, 19, 49, 27, 73이 있다

이렇게 4개씩 2개로 나눠보자

44, 88, 62, 38 그리고 19, 49, 27, 73

 

왼쪽의 44, 88, 62, 38을 또 나눠보자

44, 88 그리고 62, 38

 

오른쪽 19, 49, 27, 73도 나눠보자

19, 49 그리고 27, 73

 

이제 각자 1개씩 나눈다

44 / 88 / 62 / 38 / 19 / 49 / 27 / 73

 

병합 단계

병합 단계로 들어가면 반대로 병합해나간다

2개의 부분 집합씩 정렬

44, 88 / 38, 62 / 19, 49 / 27, 73

 

또 2개의 부분 집합씩 정렬

여기서 방법은 2개의 집합에서 맨앞의 녀석들부터 비교한다.

즉, 맨 앞의 44와 38을 먼저 비교하고,

38을 먼저 옮긴다, 그리고 44와 62를 비교, 다음 62와 88을 비교 이런식으로 흘러간다

 

그럼 이렇게 정렬이 된다

38, 44, 62, 88 그리고 19, 27, 49, 73

 

마지막으로 병합

19, 27, 38, 44, 49, 62, 73, 88

 

 

분할하는 mergeSort와 병합하는 merge 단계로 나뉜다.