합병정렬

6. 병합(합병) 정렬 (Merge Sort)

Reference : 건국대학교 컴퓨터공학과 자료구조 수업 / 김성열 교수님 합병 정렬의 개념 : 하나의 리스트를 2 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 것이다. ==> 합병 정렬은 분할 정복 (divide and conquer) 기법에 바탕을 두고 있다 분할 정복 (divide and conquer) 기법 : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략 ==> 분리된 문제가 아직도 해결하기 어렵다면 (충분히 작지 않다면) 분할 정복 방법을 연속하여 다시 적용 ==> 분할 정복 기법은 대개 순환 호출을 이용하여 구현 분할(Divide) : 입력 배열..