18. 병합(Merge) 정렬 알고리즘

1. 개요

 병합 정렬 - 분할 정복의 대표적인 예.

 분할 정복이므로 재귀적 방식으로 코딩.

 병합 정렬은 퀵 정렬의 보안적인 형태. (안정성이 퀵 정렬보다 뛰어남)

 안정성이란 간단하게 큰 부피에서 작은 부피 일로 진행되는지, 작은 부피에서 큰 부피 일로 진행되는지 차이.

 퀵 정렬은 큰 부피에서 작은 부피 일로 진행. (각 재귀 호출 이전에 작업하므로 이전 재귀 오버헤드가 쌓임)

 병합 정렬은 작은 부피에서 큰 부피 일로 진행. (각 재귀 호출이 끝나면 그 오버헤드는 종료)

 병합 정렬은 입력 데이터의 사전 정렬에 영향을 받지 않음. (최종적으로 한 하나의 데이터 단위로 나누기에.)

 병합 정렬은 연결리스트 사용 가능. (연결리스트 기반 데이터 정렬은 병합 정렬 사용)

 보통 O(nlogn)의 시간이 걸리지만 더 정확히는 최악의 경우 O(nlog^2n)이 걸림.

 알고리즘 순서

 (1) 데이터리스트를 반으로 나눈다. 최종적으로 데이터리스트 크기가 1일때까지 나눈다.

 (2) 반으로 나뉜 두 데이터리스트를 비교하여 합병한다.

 (3) 위의 과정이 반복된다.

 (합병 알고리즘은 단순 크기 비교일 뿐이지 어렵지 않다. 정말 중요한건 위의 과정을 재귀로 어떻게 나눌것인지이다.)

2. 코드

2-1) 메인

2-2) 병합 정렬 알고리즘

2-3) 출력

3. 해설

 앞의 3가지 정렬 Bubble, Selection, Insertion 정렬과 비교할 수 없는 속도를 보인다.

 앞의 O(n^2) 속도를 가진 3가지 정렬이 크기 10만 데이터 정렬 속도가 병합 정렬이 크기 1억 정렬 속도와 같다.

 크기가 1000미만이면 어떤 정렬을 사용해도 상관없다. 하지만 그 이상일 경우 O(nlogn) 정렬이 좋다.

 기억해야할 것.

 1) 병합 정렬을 위한 Index범위를 정확하게 넣어야한다. 1이라도 차이날 경우 알고리즘은 실패한다.

 2) 결국은 큰 토대는 MergeSort() 코드다. Merge()는 단순 반복 비교 연산일 뿐이다.