합병정렬

알고리듬 - 합병, 퀵, 기수 정렬

합병, 퀵, 기수 정렬은 앞서 알아본 버블, 선택, 삽입 정렬에 비해 구현이 어려운 대신 좋은 성능을 가지고 있다. 이에 대해 알아보자. 합병 정렬 합병 정렬(Merge Sort)은 분할 정복(Devide and Conquer)을 이용해 정렬을 하는 방식이다. 진행 과정은 아래와 같다. 1. 주어진 배열을 반으로 나눈다. 2. 왼쪽 배열과 오른쪽 배열을 각각 정렬한다. 3. 두 배열을 합쳐 하나의 정렬된 배열을 만든다. 합병 정렬은 배열을 각각 정렬할 때 재귀를 이용하는데 배열을 반으로 나누고 그 배열을 다시 반으로 나누면서 해결해야 하는 문제를 줄인다.(D&C) 먼저 전체 과정을 그림으로 보자. 합병 정렬은 분할 정복을 거쳐 정렬을 한다. 다음은 Merge 과정이다. 각 배열을 가리키는 포인터를 이용한..