합병정렬(Merge Sort)

합병정렬(Merge Sort)

합병정렬은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음 두개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 것입니다.

이처럼 합병정렬은 분할-정복(Divide and Conquer) 기법에 바탕을 두고 있습니다.

- 얼핏보면 쉘 정렬과 비슷해보이지만 또 그렇지만은 않습니다.

1. 분할 : 입력 배열을 같은 크기의 2개의 부분 배열로 분할합니다.

2. 정복 : 부분 배열을 정렬합니다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용해 다시 분할 정복 기법을 적용합니다.

3. 결합 : 정렬된 부분 배열들을 하나의 배열에 통합합니다.

합병정렬의 특징

삽입, 선택, 버블, 쉘 정렬 등의 이제까지 설명했던 정렬들 중 실행속도가 가장 빠릅니다. O(n log 2n)

합병정렬은 최적, 최악, 평균 속도를 가리지 않고 항상 일정한 속도를 냅니다.

단점으로는 임시 배열이 필요하다는 것

레코드들의 크기가 큰 경우에는 이동 횟수가 많으므로 시간적 낭비를 초래할 수 있습니다.

- 이 경우 레코드를 연결리스트로 구성하면 링크 인덱스만 변경되기 때문에 무시해도 됩니다.

- 연결리스트를 사용한다면 퀵 정렬을 포함해 가장 효율적인 정렬방법이 될 수 있습니다. (퀵 정렬은 다음에 포스팅 하겠습니다.)

합병정렬의 구현

출처 : http://wonjayk.tistory.com/221