병합 정렬(merge sort)은 합병정렬으로도 불리며 시간 복잡도 $O(nlogn)$ 를 가지는 굉장히 빠른 정렬 알고리즘이다. 과정은 다음과 같다. 1. 분할 2. 정복 3. 결합 4. 복사 각 과정에 대해 하나씩 설명해 보겠다. 가장 먼저 분할은 정렬되지 않은 배열을 두 부분으로 잘라서 두 개의 부분 배열로 분할하는 과정이다. 만약 배열의 원소 개수가 홀수인 경우에는 크기가 비슷하도록 분할한다. 9개면 4개, 5개로 분할할 수 있다. 두 번째 과정은 정복이다. 정복은 분할한 각 부분 배열을 재귀적으로 병합 정렬하는 과정이다. 즉, 분할한 두 개의 배열에 대하여 또다시 분할, 정복, 결합, 복사를 거치도록 하는 것이다. 분할, 정복 두 과정을 c언어 코드로 설명하자면 다음과 같다. void merge..
