합병정렬(Merge Sort) 합병정렬은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음 두개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 것입니다. 이처럼 합병정렬은 분할-정복(Divide and Conquer) 기법에 바탕을 두고 있습니다. - 얼핏보면 쉘 정렬과 비슷해보이지만 또 그렇지만은 않습니다. 1. 분할 : 입력 배열을 같은 크기의 2개의 부분 배열로 분할합니다. 2. 정복 : 부분 배열을 정렬합니다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용해 다시 분할 정복 기법을 적용합니다. 3. 결합 : 정렬된 부분 배열들을 하나의 배열에 통합합니다. 합병정렬의 특징 삽입, 선택, 버블, 쉘 정렬 등의 이제까지 설명했던 정렬들 중 ..
