병합 정렬

병합정렬

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

분할 정복(divide and conquer)기법에 바탕을 두고 있다.

1. 분할 : 입렬 배열을 같은 크기의 2개의 부분 배열로 분할

2. 정복 : 부분 배열을 정렬

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